Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 22191 Accepted
Submission(s): 6791
#include<iostream> #define MAX 100001 using namespace std; int flg[MAX]; int par[MAX]; //int find(int x){ // if (par[x] == x) // return x; // return par[x] = find(par[x]); //} int find(int x){//路径压缩查找 int r = x; while (par[r] != r)r = par[r]; int i = x, j; while (i != r){ j = par[i]; par[i] = r; i = j; } return par[x]; } int main() { int a, b, cnt = 0, num = 0; bool qualified = true; memset(flg, 0, sizeof(flg)); for (int i = 1; i < MAX; i++)par[i] = i; while (cin >> a >> b,a!=-1,b!=-1){ cnt++;//记录边的数量 flg[a] = flg[b] = 1; if (a == 0 && b == 0){ num = 0;//找一共有几个顶点 for (int i = 1; i < MAX; i++){ if (flg[i] == 1)num++; } //cout << num << "," << cnt << endl;//+++ if (num == 0){//坑爹的测试数据,0 0 也是yes cout << "Yes"; } else if (qualified && cnt==num){//顶点数一定是边数+1,因为结束时0 0cnt也加1了所以就直接==判断了 cout << "Yes"; } else{ cout << "No"; } cout << endl; cnt = 0; num = 0; qualified = true; memset(flg, 0, sizeof(flg)); for (int i = 1; i < MAX; i++)par[i] = i; continue; } a = find(a); b = find(b); if (a == b)qualified = false; else { par[a] = b; } } return 0; }
原文:http://www.cnblogs.com/littlehoom/p/3560150.html