P11674 [USACO25JAN] Reachable Pairs G题目描述考虑一个无向图包含NNN个结点编号为1…N1\dots N1…N以及MMM条边1≤N≤2⋅1051\le N\le 2\cdot 10^51≤N≤2⋅1050≤M≤4⋅1050\le M\le 4\cdot 10^50≤M≤4⋅105。给定一个位串s1s2…sNs_1s_2\dots s_Ns1​s2​…sN​。对于每一个t∈[1,N]t\in [1,N]t∈[1,N]在时刻ttt时如果st0s_t0st​0则从图中移除结点ttt。如果st1s_t1st​1则从图中移除结点ttt并在结点ttt被移除之前的每对邻居之间添加一条边。注意在这两种情况下当一个结点从图中被移除时它的所有相邻边也会被移除。计算在每一个时刻1…N1\ldots N1…N之前可以通过一组边相互到达的结点对数。输入格式输入的第一行包含NNN和MMM。第二行包含长为NNN的位串sss。以下MMM行每行包含两个整数表示图中的一条边。输出格式输出NNN行为每一个时刻之前所求的对数。输入输出样例 #1输入 #13 2 111 1 2 1 3输出 #13 1 0输入输出样例 #2输入 #23 2 000 1 2 1 3输出 #23 0 0输入输出样例 #3输入 #37 8 1101101 6 2 1 2 2 3 6 3 1 3 1 7 4 5 2 7输出 #311 7 4 2 1 1 0说明/提示样例 1 解释在移除之前所有结点对之间都可以相互到达。结点111被移除后结点222和333之间添加了一条边因此它们仍然可以相互到达。样例 2 解释在移除之前所有结点对之间都可以相互到达。结点111被移除后结点222和333之间不再可以相互到达。测试点4∼64\sim 64∼6N≤100N\le 100N≤100。测试点7∼87\sim 87∼8所有sis_isi​均等于000。测试点9∼119\sim 119∼11所有sis_isi​均等于111。测试点12∼2312\sim 2312∼23没有额外限制。C实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintMAXN2e510;intn,m,fa[MAXN],sz[MAXN];ll res,ans[MAXN];intfind(intu){returnufa[u]?u:fa[u]find(fa[u]);}inlinevoidmerge(intu,intv){ufind(u),vfind(v);if(uv)return;fa[v]u;res-(ll)sz[v]*(sz[v]-1)/2;res-(ll)sz[u]*(sz[u]-1)/2,sz[u]sz[v];res(ll)sz[u]*(sz[u]-1)/2;}inlinevoidadd(intu){ufind(u),ressz[u];}chars[MAXN];vectorintg[MAXN];intmain(){scanf(%d%d%s,n,m,s1);for(inti1;in;i)fa[i]i;for(inti1,u,v;im;i){scanf(%d%d,u,v);g[u].emplace_back(v),g[v].emplace_back(u);if(s[u]1s[v]1)merge(u,v);}for(intun;u;u--){if(~s[u]1)for(intv:g[u])if(vu||s[v]1)merge(u,v);add(u),ans[u]res;}for(inti1;in;i)printf(%lld\n,ans[i]);return0;}