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