本文共 1079 字，大约阅读时间需要 3 分钟。
删点并查集，就是用一个新的点标取代之前的点标就可以。
。 y一下就能够了
#include #include #include #include #include #include #include #include #include #include using namespace std;#define mod 1000000007#define ll int#define N 100101ll r[1100010], f[1100010], a[N], top;ll n, m;ll find(ll x){return x==f[x]?x:f[x] = find(f[x]);}void Union(ll x, ll y){ ll fx = find(x), fy = find(y); if(fx==fy) return; if(r[fx]>r[fy]) swap(fx,fy); f[fx] = fy; r[fy] += r[fx];}void Del(ll x){ find(a[x]); a[x] = top; r[top] = 1; f[top] = top; top++;}void init(){ for(ll i = 0; i < n; i++) f[i] = a[i] = i, r[i] = 1; top = n;}set s;int main(){ int i, j, u, v, Cas = 1; while(scanf("%d %d",&n,&m), n+m){ init(); while(m--) { char c[10]; scanf("%s %d",c,&u); if(c[0]=='M') { scanf("%d",&v); Union(a[u], a[v]); } else Del(u); } s.clear(); for(i = 0; i < n; i++) for(i = 0; i < n; i++) s.insert(find(a[i])); printf("Case #%d: %d\n", Cas++, s.size()); } return 0;}
转载于:https://www.cnblogs.com/wzjhoutai/p/7127936.html