Join items into groups, and answer whether two items are in the same group.
What to build
A union-find structure with a find function, driven by commands.
Requirements
- At the start, every item is in a group by itself.
U a bjoins the groups ofaandb.Q a bprintsyesifaandbare in the same group, andnoif they are not.
Input
The first line has n and q. Each of the next q lines has one command. The items are numbered 0 to n - 1.
Output
One line for each Q.
Constraints
1 ≤ n ≤ 1000 and 1 ≤ q ≤ 1000.
Example
Input:
5 5
U 0 1
U 3 4
Q 0 1
Q 1 3
Q 4 3
Output:
yes
no
yes
Why it works
Every member of a group leads up to the same root, so two items are together exactly when their roots are equal. Comparing parents is not enough, because two members of one tree can have different parents.
Examples
Example 1 · Input
5 5 U 0 1 U 3 4 Q 0 1 Q 1 3 Q 4 3
Expected output
yes no yes
Example 2 · Input
2 2 Q 0 1 Q 1 1
Expected output
no yes
Hints
Hint 1
Start with parent[i] = i for every item.
Hint 2
find(x) follows parent links until it reaches an item that is its own parent.
Hint 3
To join a and b, make the root of one group the parent of the other root. Never link a and b themselves.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int parent[1000];
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
int main(void) {
int n, q;
scanf("%d %d", &n, &q);
for (int i = 0; i < n; i++) parent[i] = i;
for (int i = 0; i < q; i++) {
char op[2];
int a, b;
scanf("%1s %d %d", op, &a, &b);
int ra = find(a), rb = find(b);
if (op[0] == 'U') {
parent[ra] = rb;
} else {
if (ra == rb) printf("yes\n");
else printf("no\n");
}
}
return 0;
}