fork(1) download 
  1. #include <stdio.h>
  2.  
  3. #define N 200005
  4.  
  5. int c[N], size[N];
  6.  
  7. int find(int x) {
  8.     if (x != c[x])
  9.         c[x] = find(c[x]);
  10.     return c[x];
  11. }
  12.  
  13. int unite(int x, int y) {
  14.     x = find(x);
  15.     y = find(y);
  16.     if (x == y) return 0;
  17.     if (size[x] < size[y]) {
  18.         int temp = x;
  19.         x = y;
  20.         y = temp;
  21.     }
  22.     c[y] = x;
  23.     size[x] += size[y];
  24.     return 1;
  25. }
  26.  
  27. void solve() {
  28.     int n;
  29.     scanf("%d", &n);
  30.  
  31.     int s_indices[n], s_count = 0;
  32.     int used[n * 2], used_count = 0;
  33.  
  34.     for (int i = 0; i < n; ++i) {
  35.         int u, v;
  36.         scanf("%d %d", &u, &v);
  37.  
  38.         if (c[u] == 0) {
  39.             c[u] = u;
  40.             size[u] = 1;
  41.             used[used_count++] = u;
  42.         }
  43.  
  44.         if (c[v] == 0) {
  45.             c[v] = v;
  46.             size[v] = 1;
  47.             used[used_count++] = v;
  48.         }
  49.  
  50.         if (unite(u, v)) {
  51.             s_indices[s_count++] = i + 1;
  52.         }
  53.     }
  54.  
  55.     printf("%d\n", s_count);
  56.     for (int i = 0; i < s_count; ++i)
  57.         printf("%d ", s_indices[i]);
  58.     printf("\n");
  59.  
  60.     for (int i = 0; i < used_count; ++i) {
  61.         int x = used[i];
  62.         c[x] = 0;
  63.         size[x] = 0;
  64.     }
  65. }
  66.  
  67. int main() {
  68.     int t;
  69.     scanf("%d", &t);
  70.     while (t--) solve();
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
2
1
1 2
4
1 2
2 3
1 3
3 5
stdout 
1
1 
3
1 2 4
https://ideone.com/zeYTx9
language:
C (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!