并查集算法

int find(int x){ if(p[x] != x) p[x] = find(p[x]); return p[x];}

#includeusing namespace std;const int N = 50005;int n,K,fake;int p[N],d[N];int find(int x){ if(p[x] != x) { int u = find(p[x]); d[x] += d[p[x]]; p[x] = u; } return p[x];}int main(){ cin>>n>>K; for(int i = 1; i <= n; i ++ ) p[i] = i; while(K--) { int t,x,y; cin>>t>>x>>y; if(x > n || y > n) fake++; else { int px = find(x),py = find(y); if(t == 1) { if(px == py && (d[y] - d[x]) % 3) fake++; if(px != py) { p[px] = py; d[px] = d[y] - d[x]; } } if(t == 2) { if(px == py && (d[x] - d[y] - 1) % 3) fake++; if(px != py) { p[px] = py; d[px] = d[y] - d[x] + 1; } } } } cout<