Submission #27546289

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

// {{{ UnionFind, DisjointSet
template<int MaxN>
class UnionFind {
  // if par[x] <  0: x is a parent and -par[x] is the size of the set
  // if par[x] >= 0: x's parent is par[x]
  int par[MaxN];
public:
  UnionFind() {
    for (int i = 0; i < MaxN; i++) {
      par[i] = -1;
    }
  }
  int root(int x) {
    if (par[x] < 0) {
      return x;
    } else {
      return par[x] = root(par[x]);
    }
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return -par[root(x)];
  }
  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) { return false; }
    if (par[x] > par[y]) {
      std::swap(x, y);
    }
    par[x] += par[y];
    par[y] = x;
    return true;
  }
};
void UnionFindSample() {
  printf("============ UnionFindSample ============\n");
  UnionFind<100> u;
  for (int i = 0; i < 34; i++) {
    u.unite(i, i*3);
  }
  for (int i = 0; i < 100; i++) {
    printf("root(%d) = %d\n", i, u.root(i));
  }
}
// }}} UnionFind, DisjointSet

int N, M;
int A[200005], B[200005];
vector<int> E[200005];

int main() {
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    cin >> A[i] >> B[i];
    A[i]--; B[i]--;
    E[min(A[i], B[i])].push_back(max(A[i], B[i]));
  }

  int k = 0;
  vector<int> v;
  UnionFind<200005> u;
  for (int i = N-1; i >= 0; i--) {
    v.push_back(k);
    k++;
    // printf("i = %d: ", i);
    for (int j = 0; j < E[i].size(); j++) {
      int n = E[i][j];
      // printf("%d, ", n);
      int oi = u.root(i), on = u.root(n);
      if (n > i) {
        u.unite(i, n);
      }
      if (u.root(i) != oi || u.root(n) != on) {
        k--;
      }
    }
    // printf(" ## ");
    // for (int j = 0; j < N; j++) { printf("%d -> %d, ", j, u.root(j)); } puts("");
  }
  for (int i = 0; i < v.size(); i++) {
    cout << v[v.size()-1-i] << endl;
  }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:73:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   73 |     for (int j = 0; j < E[i].size(); j++) {
      |                     ~~^~~~~~~~~~~~~
./Main.cpp:87:21: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   87 |   for (int i = 0; i < v.size(); i++) {
      |                   ~~^~~~~~~~~~

Judge Result