C++解答

#include <iostream>
#include <cstdio>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N = 200001;
struct edge{
	int to, pre;
}e[N];
int l = 0, u[N], sz[N];
void ins(int a, int b){
	e[++l] = (edge){b, u[a]}, u[a] = l;
}
#define reg(i,a) for(int i=u[a];i;i=e[i].pre)
#define v e[i].to
int f[N];
int find(int x){
	return f[x] == x ? x : f[x] = find(f[x]);
}
int list[N], L = 0;
void init(){
	l = 0;
	rep(i,0, L - 1) {
		int x = list[i];
		f[x] = x, u[x] = 0, sz[x] = 1;
	}
	L = 0;
}
int ans1[N], T = 0;
int main(){
	int tp, a, b, ans = 0, flag = 0;
	rep(i,1,N - 1) sz[i] = 1, f[i] = i;
	while (scanf("%d%d%d", &a, &b, &tp) == 3)
	{
		list[L++] = a, list[L++] = b;	
		if (tp == 1){
			a = find(a), b = find(b);
			if (a == b) {ans++;continue;}
			if (sz[a] > sz[b]) swap(a,b);
			int j = 0;
			reg(i,a) if ((v = find(v)) == b) {flag = 1; break;} else j = i; 
			if (!flag){
				f[a] = b; 
				if (u[a]){
					e[j].pre = u[b];
					u[b] = u[a];
				}
				sz[b] += sz[a];
			}
		}else{
			a = find(a), b = find(b);
			if (a != b) ins(a, b), ins(b, a); else flag = 1;
		}
		if (flag) flag = 0, ans++, ans1[++T] = ans, ans = 0, init(); else ans++;
	}
	printf("%d\n",T);
	rep(i,1,T) printf("%d\n",ans1[i]);
	return 0;
}