Posted in DSU

HDU 1213/ kuangbin 5-C

10/16/2017
Problem: http://acm.split.hdu.edu.cn/showproblem.php?pid=1213


#include<iostream>
#include<string.h>
using namespace std;

int parent[1005] = {0};
int cnt = 0;

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p1] = p2;
		cnt --;
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		cnt =0;
		int n, m;
		cin >> n >> m;
		cnt = n;
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		}
		for (int i = 1; i <= m; i++) {
			int a, b;
			cin >> a >> b;
			if (find(a) != find(b)) {
				merge(a, b);
			}
		}
		cout << cnt << endl;
	}
	return 0;
} 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s