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

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

alliance.out

No
3

题解：　　

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

　　因为如果把暴力进行改进把边双缩树（这一步可以不必要进行），那么显然加的边上的两点到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=,tag=;}

}ee[MAXN*];

struct e{

    int first,next,to;

}a[MAXN*];

int f[MAXN],fa[MAXN],sz[MAXN],last[MAXN],dep[MAXN];

int n,m,p,num=;

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=;i<=m;i++){

        int x,y;scanf("%d%d",&x,&y);

        ee[i].from=x,ee[i].to=y;

    }

    for(int i=;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=;

    }

    m+=p;

}

void build(){

    for(int i=;i<=n;i++) f[i]=i;

    for(int i=;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=;

        }

    }

}

void dfs(int now,int father){

    dep[now]=dep[father]+;

    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=;i<=n;i++) fa[i]=i;

    for(int i=;i<=n;i++) sz[i]=;

    for(int i=;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=;i<=n;i++) if(!dep[i]) dfs(i,i);

    work();

    return ;

}

巴特西

JZOJ 3875 星球联盟

最新文章

热门文章