bzoj4998 星球联盟

Description

在遥远的S星系中一共有N个星球，编号为1…N。其中的一些星球决定组成联盟，以方便相互间的交流。但是，组成

联盟的首要条件就是交通条件。初始时，在这N个星球间有M条太空隧道。每条太空隧道连接两个星球，使得它们能

够相互到达。若两个星球属于同一个联盟，则必须存在一条环形线路经过这两个星球，即两个星球间存在两条没有

公共隧道的路径。为了壮大联盟的队伍，这些星球将建设P条新的太空隧道。这P条新隧道将按顺序依次建成。一条

新轨道建成后，可能会使一些星球属于同一个联盟。你的任务是计算出，在一条新隧道建设完毕后，判断这条新轨

道连接的两个星球是否属于同一个联盟，如果属于同一个联盟就计算出这个联盟中有多少个星球。

Input

第1行三个整数N，M和P，分别表示总星球数，初始时太空隧道的数目和即将建设的轨道数目。

第2至第M+1行，每行两个整数，表示初始时的每条太空隧道连接的两个星球编号。

第M+2行至第M+P+1行，每行两个整数，表示新建的太空隧道连接的两个星球编号。

这些太空隧道按照输入的顺序依次建成。

1≤N,M,P≤200000

Output

输出共P行。

如果这条新的太空隧道连接的两个星球属于同一个联盟，就输出一个整数，表示这两个星球所在联盟的星球数。

如果这条新的太空隧道连接的两个星球不属于同一个联盟，就输出"No"（不含引号）。

Sample Input

5 3 4
1 2
4 3
4 5
2 3
1 3
4 5
2 4

Sample Output

No
3
2
5

HINT

正解：并查集。

这题可以离线，于是我们首先可以用一个并查集把连通关系处理出来。

如果连边的时候两点不连通，那么答案肯定为$No$。

否则我们标记一下，这条路径肯定就强连通了。

然后我们可以处理出一个森林，这时我们再重新处理一下那些强连通的边。

直接把两点间路径形成的强连通块用另一个并查集并起来就行了，与跳$lca$的操作类似。

答案就是这个点所在的强连通块的点数。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define N (500010)
 6 
 7 using namespace std;
 8 
 9 struct edge{ int nt,to; }g[N<<1];
10 
11 int head[N],sz[N],f[N],fa[N],dep[N],a[N],b[N],qu[N],q[N],n,m,p,num;
12 
13 il int gi(){
14   RG int x=0,q=1; RG char ch=getchar();
15   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
16   if (ch=='-') q=-1,ch=getchar();
17   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
18   return q*x;
19 }
20 
21 il void insert(RG int from,RG int to){
22   g[++num]=(edge){head[from],to},head[from]=num; return;
23 }
24 
25 il void bfs(RG int S){
26   RG int h=0,t=1; q[t]=S,dep[S]=1;
27   while (h<t){
28     RG int x=q[++h],v;
29     for (RG int i=head[x];i;i=g[i].nt){
30       v=g[i].to; if (dep[v]) continue;
31       q[++t]=v,dep[v]=dep[x]+1,fa[v]=x;
32     }
33   }
34   return;
35 }
36 
37 il int find(RG int x){
38   return f[x]==x ? x : f[x]=find(f[x]);
39 }
40 
41 il void merge(RG int x,RG int y){
42   x=find(x),y=find(y);
43   while (x^y){
44     if (dep[x]<dep[y]) swap(x,y);
45     sz[find(fa[x])]+=sz[x];
46     x=f[x]=find(fa[x]);
47   }
48   return;
49 }
50 
51 int main(){
52 #ifndef ONLINE_JUDGE
53   freopen("alliance.in","r",stdin);
54   freopen("alliance.out","w",stdout);
55 #endif
56   n=gi(),m=gi(),p=gi();
57   for (RG int i=1;i<=n;++i) f[i]=i;
58   for (RG int i=1,x,y;i<=m+p;++i){
59     a[i]=gi(),b[i]=gi(),x=find(a[i]),y=find(b[i]);
60     if (x!=y) qu[i]=1,f[x]=y,insert(a[i],b[i]),insert(b[i],a[i]);
61   }
62   for (RG int i=1;i<=n;++i){ if (!dep[i]) bfs(i); f[i]=i,sz[i]=1; }
63   for (RG int i=1;i<=m;++i) if (!qu[i]) merge(a[i],b[i]);
64   for (RG int i=m+1;i<=m+p;++i)
65     if (qu[i]) puts("No");
66     else merge(a[i],b[i]),printf("%d
",sz[find(a[i])]);
67   return 0;
68 }