BOJ 25172 - 꼼꼼한 쿠기의 졸업여행

BOJ 25172 - 꼼꼼한 쿠기의 졸업여행

끊어지는 순서 반대로 생각해서 DSU로 이어주는 것으로 스위핑하는 문제이다.

struct DSU {
   vector<int> p;
   DSU(int n) : p(n, -1) {}
   int gp(int n) {
      if (p[n] < 0) return n;
      return p[n] = gp(p[n]);
   }
   void merge(int a, int b, int to_b = 0) {
      a = gp(a), b = gp(b);
      if (a == b) return;
      if (!to_b && size(a) > size(b)) swap(a, b);
      p[b] += p[a];
      p[a] = b;
   }
   bool is_merged(int a, int b) { return gp(a) == gp(b); }
   int size(int n) { return -p[gp(n)]; }
};
void solve() {
   int n, m;
   cin >> n >> m;
   DSU dsu(n);
   vvi edges(n);
   for (int i = 0, u, v; i < m; i++) {
      cin >> u >> v, u--, v--;
      edges[u].pb(v), edges[v].pb(u);
   }
   vi ans(n + 1);
   vi qry(n);
   fv(qry);
   for (int &i: qry) i--;
   vi live(n);
   for (int i = n - 1, c = 1; i >= 0; i--, c++) {
      live[qry[i]] = 1;
      for (int j: edges[qry[i]]) {
         if (live[j])
            dsu.merge(qry[i], j);
      }
      debug(dsu.size(qry[i]));
      if (dsu.size(qry[i]) == c)
         ans[i] = 1;

   }
   for (int i = 0; i <= n; i++) {
      if (!ans[i]) cout << "DIS";
      cout << "CONNECT\n";
   }
}