JZOJ 3875 星球联盟

星球联盟"/>

JZOJ 3875 星球联盟

【问题描述】
在遥远的 S 星系中一共有 N 个星球，编号为 1…N。其中的一些星球决定组成联盟，
以方便相互间的交流。
但是，组成联盟的首要条件就是交通条件。初始时，在这 N 个星球间有 M 条太空
隧道。每条太空隧道连接两个星球，使得它们能够相互到达。若两个星球属于同一个联
盟，则必须存在一条环形线路经过这两个星球，即两个星球间存在两条没有公共隧道的
路径。
为了壮大联盟的队伍，这些星球将建设 P 条新的太空隧道。这 P 条新隧道将按顺序
依次建成。一条新轨道建成后，可能会使一些星球属于同一个联盟。你的任务是计算出，
在一条新隧道建设完毕后，判断这条新轨道连接的两个星球是否属于同一个联盟，如果
属于同一个联盟就计算出这个联盟中有多少个星球。
【输入格式】
第 1 行三个整数 N，M 和 P，分别表示总星球数，初始时太空隧道的数目和即将建
设的轨道数目。
第 2 至第 M+1 行，每行两个整数，表示初始时的每条太空隧道连接的两个星球编
号。
第 M+2 行至第 M+P+1 行，每行两个整数，表示新建的太空隧道连接的两个星球编
号。这些太空隧道按照输入的顺序依次建成。
【输出格式】
输出共 P 行。如果这条新的太空隧道连接的两个星球属于同一个联盟，就输出一个
整数，表示这两个星球所在联盟的星球数。如果这条新的太空隧道连接的两个星球不属
于同一个联盟，就输出”No”（不含引号） 。
【样例 1】
alliance.in
3 2 1
1 2
1 3
2 3

alliance.out

3

alliance.in
5 3 4
1 2
4 3
4 5
2 3
1 3
4 5
2 4

alliance.out

No
3

2

5

题解：　　

　　这个题目，第一眼看上去就是一个双联通分量，但是很明显双联通分量，但是只能跑出４０分，所以需要换思路，发现每次重构算了很多不需要算的边双联通分量，所以我们可以只关注要连边的那两个点，首先我们可以先把整个图（包括要加入的边）扣出一颗树来，为什么要想到树呢？

　　因为如果把暴力进行改进把边双缩树（这一步可以不必要进行），那么显然加的边上的两点到lca的路径上的所有点都会形成一个环，那么这次询问的答案就是这个环的size,那么我们就可以把这个环缩成一个点，但怎么快速缩点？将所以的点用并查集的方式指向lca就可以了，答案就是lca的size(在并查集中的)。

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define MAXN 200100
using namespace std;
struct edge{int from,to,flag,tag;edge(){flag=0,tag=0;}
}ee[MAXN*2];
struct e{int first,next,to;
}a[MAXN*2];
int f[MAXN],fa[MAXN],sz[MAXN],last[MAXN],dep[MAXN];
int n,m,p,num=0;void addedge(int from,int to){a[++num].to=to;a[num].next=a[from].first;a[from].first=num;
}int find(int x){if(f[x]!=x) f[x]=find(f[x]);return f[x];
}int find2(int x){if(fa[x]!=x) fa[x]=find2(fa[x]);return fa[x];
}void conbine(int x,int y){int xx=find(x),yy=find(y);if(xx!=yy) f[xx]=yy;
}void conbine2(int x,int y){int xx=find2(x),yy=find2(y);if(fa[xx]!=fa[yy]) {fa[xx]=yy;sz[yy]+=sz[xx];}
}void init(){scanf("%d%d%d",&n,&m,&p);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);ee[i].from=x,ee[i].to=y;}for(int i=1;i<=p;i++){int x,y;scanf("%d%d",&x,&y);ee[i+m].from=x,ee[i+m].to=y,ee[i+m].tag=1;}m+=p;
}void build(){for(int i=1;i<=n;i++) f[i]=i;for(int i=1;i<=m;i++){int x=ee[i].from,y=ee[i].to;if(find(x)!=find(y)){addedge(x,y),addedge(y,x);conbine(x,y);ee[i].flag=1;}}
}void dfs(int now,int father){dep[now]=dep[father]+1;last[now]=father;for(int i=a[now].first;i;i=a[i].next){int to=a[i].to;if(dep[to]) continue;dfs(to,now);}
}int dfs1(int x,int y){x=find2(x),y=find2(y);if(x==y) return x;int lca;if(dep[x]>dep[y]){lca=dfs1(last[x],y);conbine2(x,lca);}else {lca=dfs1(x,last[y]);conbine2(y,lca);}return lca;
}void work(){for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=n;i++) sz[i]=1;for(int i=1;i<=m;i++){if(ee[i].flag){if(ee[i].tag)printf("No\n");continue;}dfs1(ee[i].from,ee[i].to);if(ee[i].tag) printf("%d\n",sz[find2(ee[i].from)]);}
}int main()
{init();build();for(int i=1;i<=n;i++) if(!dep[i]) dfs(i,i);work();return 0;
}

转载于:.html