HDU 3926 Hand in Hand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int maxn = 10001;

vector<int> ring1, ring2;
vector<int> link1, link2;
int f[maxn+10];
int cnt[maxn+10];
int gn, gm;
int n, m;

int getFather(int x) {
    if(x == f[x]) return x;
    else return f[x] = getFather(f[x]);
}

bool work()
{
    int Size1 = ring1.size();
    int Size2 = ring2.size();
    if(Size1 != Size2) return false;
    else {
        for(int i = 0; i < (int)Size1; i++) {
            if(ring1[i] == ring2[i]) continue;
            else return false;
        }
    }
    Size1 = link1.size();
    Size2 = link2.size();
    if(Size1 != Size2) return false;
    else {
        for(int i = 0; i < Size1; i++) {
            if(link1[i] == link2[i]) continue;
            else return false;
        }
    }
    return true;
}


int main()
{
	int T;
	int x, y;
	scanf("%d", &T);
	for(int t = 1; t <= T; t++) {
		for(int i = 1; i < maxn; i++) {
			 f[i] = i;
			 cnt[i] = 1;
		}
		ring1.clear();
		link1.clear();
		scanf("%d%d", &gn, &gm);
		for(int i = 0; i < gm; i++) {
			scanf("%d%d", &x, &y);
			int t1 = getFather(x);
			int t2 = getFather(y);
			if(t1 != t2) {
				f[t1] = t2;
				cnt[t2] += cnt[t1];
			} else {
				f[t1] = -1;
				ring1.push_back(cnt[t1]);
			}
		}
		for(int i = 1; i <= gn; i++) {
			if(f[i] == i)  {
				link1.push_back(cnt[i]);
			}
		}

        ring2.clear(); link2.clear();
		for(int i = 1; i < maxn; i++) {
			f[i] = i; cnt[i] = 1;
		}
		scanf("%d%d", &gn, &gm);
		for(int i = 0; i < gm; i++) {
			scanf("%d%d", &x, &y);
			int t1 = getFather(x);
			int t2 = getFather(y);
			if(t1 != t2) {
				f[t1] = t2;
				cnt[t2] += cnt[t1];
			} else {
				f[t1] = -1;
				ring2.push_back(cnt[t1]);
			}
		}
		for(int i = 1; i <= gn; i++) {
			if(f[i] == i) link2.push_back(cnt[i]);
		}
		sort(link1.begin(), link1.end());
		sort(ring1.begin(), ring1.end());
		sort(link2.begin(), link2.end());
		sort(ring2.begin(), ring2.end());
		bool res = work();
		if(res) printf("Case #%d: YES\n", t);
		else printf("Case #%d: NO\n", t);
	}
	return 0;
}

HDU 3926 Hand in Hand,布布扣,bubuko.com

HDU 3926 Hand in Hand

原文：http://blog.csdn.net/achiberx/article/details/21648559