algorithm/DSU.cpp at master · phanthaiduong22/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>

using namespace std;
#define MAX 30000
int parent[MAX + 5];
int ranks[MAX + 5];
int d[MAX + 5];
void makeSet()
{
	for (int i = 0; i <= MAX; i++)
	{
		parent[i] = i;
		ranks[i] = 0;
		d[i] = 0;
	}
}
int findSet(int u)
{
	if (parent[u] != u)
		parent[u] = findSet(parent[u]);
	return parent[u];
}
void unionSet(int u, int v)
{
	int up = findSet(u);
	int vp = findSet(v);
	if (up == vp)
		return;
	if (ranks[up] > ranks[vp])
		parent[vp] = up;
	else if (ranks[up] < ranks[vp])
		parent[up] = vp;
	else
	{
		parent[up] = vp;
		ranks[vp]++;
	}
}
int main()
{
	freopen("friends.inp", "r", stdin);
	freopen("friends.out", "w", stdout);
	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		int n, m, max, u, v, temp;
		max = 0;
		cin >> n >> m;
		makeSet();
		for (int j = 0; j < m; j++)
		{
			cin >> u >> v;
			unionSet(u, v);
		}
		for (int j = 1; j <= n; j++)
		{
			int temp = findSet(j);
			d[temp]++;
			if (d[temp] > max)
				max = d[temp];
		}
		cout << max << endl;
	}
}