Watch a network being built one cable at a time, and spot the cables that were not needed.
What to build
A union-find structure that processes edges in order and reports two facts.
Requirements
- An edge closes a cycle when its two ends were already connected before it arrived. Count those edges.
- Find the number of the first edge after which every vertex is connected to every other. Edges are numbered from 1.
- Print the count on the first line, and the edge number, or -1 if the graph never becomes connected, on the second.
Input
The first line has n and m. Each of the next m lines has an edge u v. The vertices are numbered 0 to n - 1.
Output
Two lines.
Constraints
2 ≤ n ≤ 1000 and 0 ≤ m ≤ 1000.
Example
Input:
4 5
0 1
1 2
0 2
2 3
3 0
Output:
2
4
Why it works
An edge between two vertices of one group adds a second route between them, which is a cycle. Every other edge merges two groups, so the graph is connected at the moment the number of groups reaches 1.
Examples
Example 1 · Input
4 5 0 1 1 2 0 2 2 3 3 0
Expected output
2 4
Example 2 · Input
3 1 0 1
Expected output
0 -1
Hints
Hint 1
Keep the number of groups, starting at n.
Hint 2
For each edge, find both roots. Equal roots mean the edge closes a cycle.
Hint 3
Different roots mean a real union: join them, subtract one group, and check whether one group is left.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int parent[1000], size[1000];
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 = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
int groups = n, cycles = 0, connected_at = -1;
for (int e = 1; e <= m; e++) {
int a, b;
scanf("%d %d", &a, &b);
a = find(a);
b = find(b);
if (a == b) {
cycles++;
continue;
}
if (size[a] < size[b]) {
int t = a;
a = b;
b = t;
}
parent[b] = a;
size[a] += size[b];
groups--;
if (groups == 1) connected_at = e;
}
printf("%d\n%d\n", cycles, connected_at);
return 0;
}