A class has n students, numbered 1 to n, and a list of friendships. Friends of friends belong to the same group. Print how many groups there are and how many students are in the largest one. Use union-find.
What to build
A union-find structure that joins friends into groups and keeps the size of each group.
Requirements
- Start with every student alone in a group.
- Join two groups only when their roots differ, hanging the smaller under the larger.
- Print the number of groups and the size of the largest.
Input
A line with n and m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000). Then m lines, each with two student numbers a and b: they are friends. A pair may repeat, and a may equal b.
Output
One line: the number of groups and the size of the largest group, separated by a space.
Constraints
1 ≤ n ≤ 1000 and 0 ≤ m ≤ 1000.
Example
Input:
5 3
1 2
2 3
4 5
Output:
2 3
Why it works
Two students are in one group exactly when they have the same root. Each union of two different roots lowers the number of groups by one.
Examples
5 3 1 2 2 3 4 5
2 3
4 0
4 1
Hints
Hint 1
Start with parent[i] = i and size[i] = 1 for every student, and n groups.
Hint 2
For each friendship, find both roots. If they differ, hang the smaller tree under the bigger, add the sizes, and subtract one group.
Hint 3
At the end, the largest group is the biggest size[r] among the roots r (where find(r) == r).
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int parent[1001], size[1001];
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
int main(void) {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
parent[i] = i;
size[i] = 1;
}
int groups = n;
for (int e = 0; e < m; e++) {
int a, b;
scanf("%d %d", &a, &b);
a = find(a);
b = find(b);
if (a == b) continue;
if (size[a] < size[b]) {
int t = a;
a = b;
b = t;
}
parent[b] = a;
size[a] += size[b];
groups--;
}
int largest = 0;
for (int i = 1; i <= n; i++)
if (find(i) == i && size[i] > largest) largest = size[i];
printf("%d %d\n", groups, largest);
return 0;
}