[LUOGU] P1536 村村通

题目描述

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府“村村通工程”的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

输入输出格式

输入格式：

每个输入文件包含若干组测试测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目N（N<1000）和道路数目M；随后的M行对应M条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从1到N编号。

注意：两个城市间可以有多条道路相通。例如：

3 3 1 2 1 2 2 1 这组数据也是合法的。当N为0时，输入结束。

输出格式：

对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。

输入输出样例

输入样例#1： 复制

4 2

1 3

4 3

3 3

1 2

1 3

2 3

5 2

1 2

3 5

999 0

0

输出样例#1： 复制

1

0

2

998

找联通块数量，由于只考虑能否到达，所以每个联通块可以视为一个点。

答案即为联通块数-1。

统计联通块数除了找父节点还有什么好办法呢..?

//Writer:GhostCai && His Yellow Duck

#include<iostream>

#include<cstring>

#define MAXN 200000

using namespace std;

int m,n,ans;

bool book[MAXN];

int fa[MAXN];

int fnd(int x){

    if(fa[x]==x) return x;

    return fa[x]=fnd(fa[x]);

}

void cat(int x,int y){

    x=fnd(x);

    y=fnd(y);

    if(x!=y) fa[y]=x;

}

struct Edge{

    int to,next;

}e[MAXN];

int ecnt,head[MAXN];

void add(int x,int y){

    e[++ecnt].to = y;

    e[ecnt].next = head[x];

    head[x]=ecnt;

}

int main(){

    while(cin>>n){

        if(!n) return 0;

        cin>>m;

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

        memset(head,-1,sizeof(head));

        memset(book,0,sizeof(book));

        ecnt=ans=0;

        int x,y;

        for(int i=1;i<=m;i++){

            cin>>x>>y;

            add(x,y);

            add(y,x);

        }

        for(int i=1;i<=n;i++){

            for(int j=head[i];j!=-1;j=e[j].next){

                int v=e[j].to ;

                cat(i,v);

            }

        }

        for(int i=1;i<=n;i++) book[fnd(i)]=1;

        for(int i=1;i<=n;i++) if(book[i]) ans++;

        if(ans!=0)

        cout<<ans-1<<endl;

        else cout<<0<<endl;

    }

}