codes/dsu.cpp at master · vntshh/codes · 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
#include<bits/stdc++.h>
using namespace std;

struct nodes {
	int parent, setsize;
};

struct edge {
	int start, end;
};

nodes node[10];

int findroot(int temp) {
	if(node[temp].parent != temp)
		node[temp].parent = findroot(node[temp].parent);
	return node[temp].parent;
}

void takeunion(int x, int y) {
	int xroot = findroot(x), yroot = findroot(y);
	if(node[xroot].setsize >= node[yroot].setsize)
		node[yroot].parent = xroot;
	else node[xroot].parent = yroot;
	node[xroot].setsize = node[yroot].setsize = node[xroot].setsize + node[yroot].setsize;
}

int main() {
	for(int i = 0; i < 10; i++) {
		node[i].parent = i;
		node[i].setsize = 1;
	}
	int n;
	cin>>n;
	for(int i = 0; i < n; i++) {
		int a, b;
		cin>>a>>b;
		takeunion(a,b);
	}
	for(int i = 0; i < n; i++) {
		int a, b;
		cin>>a>>b;
		if(findroot(a) == findroot(b)) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}