fork(1) download 
  1. using namespace std;
  2. #include <bits/stdc++.h>
  3. #define mapii map<int, int>
  4. #define debug(a) cout << #a << ": " << a << endl
  5. #define fdto(i, r, l) for(int i = r; i >= l; --i)
  6. #define fto(i, l, r) for(int i = l; i <= r; ++i)
  7. #define forit(it, type, var) for(type::iterator it = var.begin(); it != var.end(); it++)
  8. #define ii pair<int, int>
  9. #define iii pair<int, ii>
  10. #define fi first
  11. #define se second
  12. #define mp make_pair
  13. #define pb push_back
  14. #define ll long long
  15. #define maxN 200005
  16.  
  17. int n, q, pset[maxN], contain[maxN], box[maxN];
  18.  
  19. void initSet() {
  20.     fto(i, 1, n) pset[i] = i, contain[i] = i;
  21. }
  22.  
  23. int findSet(int i) {
  24.     return (pset[i] == i) ? i : pset[i] = findSet(pset[i]);
  25. }
  26.  
  27. void unionSet(int i, int j) {
  28.     pset[findSet(i)] = findSet(j);
  29. }
  30.  
  31. bool isSameSet(int i, int j) {
  32.     return (findSet(i) == findSet(j));
  33. }
  34.  
  35. int main () {
  36.     #ifndef ONLINE_JUDGE
  37.         freopen("input.txt", "r", stdin);
  38.         //freopen("output.txt", "w", stdout);
  39.     #endif // ONLINE_JUDGE
  40.  
  41.     scanf("%d%d", &n, &q);
  42.     initSet();
  43.  
  44.     fto(i, 1, q) {
  45.         int s, t;
  46.         scanf("%d%d", &s, &t);
  47.         int u = contain[s], v = contain[t];
  48.         contain[s] = 0;
  49.         if (v != 0) unionSet(u, v);
  50.         else contain[t] = u;
  51.     }
  52.  
  53.     fto(i, 1, n) box[contain[i]] = i;
  54.  
  55.     fto(i, 1, n) printf("%d ", box[findSet(i)]);
  56.  
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0s 5804KB
comments (?)
stdin 
5 4
1 2
3 2
4 2
2 5
stdout 
5 5 5 5 5
https://ideone.com/Te3wS9
1st Hunger Game - D. Hamro and Tools
language:
C++ (gcc 8.3)
created:
9 years 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!