usaco 1042 fcolor

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define fi first
#define se second
#define inf (INT_MAX/2-1)
#define infl (1LL<<60)
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) begin(a),end(a)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa
#define dbgs(x) cerr<<(#x)<<"[stl]: ";for(auto _:x)cerr<<_<<' ';cerr<<'\n',aaa
#define dbgp(x) cerr<<(#x)<<": "<<x.fi<<' '<<x.se<<'\n',aaa
#define maxn 200000

using namespace std;

ifstream fin ("fcolor.in");
ofstream fout ("fcolor.out");

int n;
vi g[maxn+5];
int sol[maxn+5];
queue<int> qu;

struct DSU {
  DSU () {}
  vi sef[maxn+5]; ///sef[i] = pe cine a mancat i, de fapt sz(sef[i]) = sy[i]
  int tata[maxn+5]; ///tata[i] = de cine a fost mancat i
  void rest () {
    for (int i = 1; i <= n; i++) {
      tata[i] = i;
      sef[i].pb(i);
    }
  }
  int afla (int x) {
    int r = x, aux;
    while (tata[r] != r) r = tata[r];
    while (x != r) {
      aux = tata[x];
      tata[x] = r;
      x = aux;
    }
    return r;
  }
  void uneste (int a, int b) {
    a = afla(a); b = afla(b);
    if (a == b) return;
    if (sz(sef[a]) < sz(sef[b])) swap(a, b);
    for (int x: sef[b]) {
      tata[x] = a; ///<- de asta nu trebuie sa te ocupi si de gt V
      sef[a].pb(x);
    }
    sef[b].clear();
    g[a].insert(g[a].end(), g[b].begin(), g[b].end());
    g[b].clear();
    if (sz(g[a]) > 1) qu.push(a);
  }
};

DSU dsu;

int main () {
  int m; fin >> n >> m;
  int i, j, z, a, b;
  for (i = 0; i < m; i++) {
    fin >> a >> b;
    g[a].pb(b);
  }
  dsu.rest();
  for (i = 1; i <= n; i++)
    if (sz(g[i]) > 1) qu.push(i);
  while (!qu.empty()) {
    int nod = qu.front();
    if (sz(g[nod]) > 1) {
      int nn = g[nod].back();
      g[nod].pop_back();
      if (dsu.afla(nn) != dsu.afla(g[nod].back())) dsu.uneste(nn, g[nod].back());
    } else qu.pop();
  }
  for (z = 1, i = 1; i <= n; i++) {
    j = dsu.afla(i);
    if (sol[j] == 0) sol[j] = z++;
    sol[i] = sol[j];
  }
  for (i = 1; i <= n; i++) fout << sol[i] << '\n';
  fin.close(); fout.close();
  return 0;
}