P11674 [USACO25JAN] Reachable Pairs G
题目描述
考虑一个无向图，包含 \(N\) 个结点，编号为 \(1\dots N\)，以及 \(M\) 条边（\(1\le N\le 2\cdot 10^5\)，\(0\le M\le 4\cdot 10^5\)）。给定一个位串 \(s_1s_2\dots s_N\)。对于每一个 \(t\in [1,N]\)，在时刻 \(t\) 时，
- 如果 \(s_t=0\)，则从图中移除结点 \(t\)。
- 如果 \(s_t=1\)，则从图中移除结点 \(t\)，并在结点 \(t\) 被移除之前的每对邻居之间添加一条边。
注意在这两种情况下，当一个结点从图中被移除时它的所有相邻边也会被移除。
计算在每一个时刻 \(1\ldots N\) 之前，可以通过一组边相互到达的结点对数。
输入格式
输入的第一行包含 \(N\) 和 \(M\)。
第二行包含长为 \(N\) 的位串 \(s\)。
以下 \(M\) 行，每行包含两个整数，表示图中的一条边。
输出格式
输出 \(N\) 行，为每一个时刻之前所求的对数。
输入输出样例 #1
输入 #1
3 2
111
1 2
1 3
输出 #1
3
1
0
输入输出样例 #2
输入 #2
3 2
000
1 2
1 3
输出 #2
3
0
0
输入输出样例 #3
输入 #3
7 8
1101101
6 2
1 2
2 3
6 3
1 3
1 7
4 5
2 7
输出 #3
11
7
4
2
1
1
0
说明/提示
样例 1 解释：
在移除之前，所有结点对之间都可以相互到达。结点 \(1\) 被移除后，结点 \(2\) 和 \(3\) 之间添加了一条边，因此它们仍然可以相互到达。
样例 2 解释：
在移除之前，所有结点对之间都可以相互到达。结点 \(1\) 被移除后，结点 \(2\) 和 \(3\) 之间不再可以相互到达。
- 测试点 \(4\sim 6\)：\(N\le 100\)。
- 测试点 \(7\sim 8\)：所有 \(s_i\) 均等于 \(0\)。
- 测试点 \(9\sim 11\)：所有 \(s_i\) 均等于 \(1\)。
- 测试点 \(12\sim 23\)：没有额外限制。
解题报告
首先，当 \(s_t==1\) 时，实际上并没有改变整个图的连通性，所以可以将这个点虚化不统计入答案而不需要真正删除。
那么现在的操作是：按编号升序删除或虚化每个点。
改成反向遍历，将每个点先虚化或删除，于是变成按编号降序加入或实化当前点。
假设遍历到点 \(u\)，那么对于每条边 \((u,v)\)，另一个端点 \(v\) 满足 \(v>u\) 或者点 \(v\) 是虚点，直接合并两个端点所在连通块。
用并查集维护连通性，同时维护每个连通块中的实点个数，在维护连通块的同时更新并答案。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
const int N=201100;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }return f*x;
}vector<int> e[N];
char s[N];
int n,m;
int ans[N],tot;int dad[N],siz[N];int findset(int x)
{if(dad[x]==x) return x;return dad[x]=findset(dad[x]);
}void mergeset(int u,int v)
{u=findset(u),v=findset(v);if(u==v) return ;tot+=siz[u]*siz[v];siz[u]+=siz[v];dad[v]=u;
}void addpos(int u)
{u=findset(u);tot+=siz[u];siz[u]++;
}signed main()
{n=read(),m=read();scanf("%s",s+1);for(int i=1;i<=n;i++) dad[i]=i;for(int i=1;i<=m;i++){int u=read(),v=read();e[u].push_back(v);e[v].push_back(u);if(s[u]=='1' && s[v]=='1')mergeset(u,v);}for(int i=n;i>=1;i--){for(auto j:e[i])if(j>i || s[j]=='1')mergeset(i,j);addpos(i);ans[i]=tot;}for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);return 0;
}