ZZULIOJ 1881: 蛤玮的机房【并查集】

柔光的暖阳◎ 2022-07-30 15:27 125阅读 0赞

## 1881: 蛤玮的机房 ##

Time Limit: 1 Sec Memory Limit: 128 MB  
Submit: 294 Solved: 104  
  
[Submit][] [Status][] [Web Board][]

## Description ##

**蛤玮成为了实验室主任,现在学校要求他建好一个机房里的通信网络.这个网络中有n台主机，现在已知建设好了m条线路，可以让一些主机直接或间接通信，为了使这n台主机互相之间都可以直接或间接通信，请问蛤玮最少还需建设多少条线路。**

**间接通信指：若A,B可以直接通信，B,C可以直接通信，则A,C可以间接通信，同理若C,D可以直接通信，A,D也可以间接通信。**

## Input ##

**输入第一行为一个整数T(1<=T<=10)，代表数据组数。对于每组数据，第一行为两个整数n(1<=n<=100),m(1<=m<=n\*n)，接下来m行每行两个整数u,v(1<=u,v<=n)，表示主机u,v之间已建立线路。**

## Output ##

**对于每组数据，输出一个整数，表示还需建设的线路数。**

## Sample Input ##

3 3

1 1

2 1

1 2

## Sample Output ##

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int n,m;
    int t;
    int per[50000];
    void init()
    {
    	int i,j;
    	for(i=1;i<=n;i++)
    	{
    		per[i]=i;
    	}
    }
    int find(int x)
    {
    	int r=x;
    	while(per[r]!=r)
    	{
    		r=per[r];
    	}
    	return r;
    }
    void join(int x,int y)
    {
    	int fx=find(x);
    	int fy=find(y);
    	if(fx!=fy)
    	{
    		per[fx]=fy;
    	}
    }
    int main()
    {
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d%d",&n,&m);
    		init();
    		int i,j;
    		for(i=0;i<m;i++)
    		{
    			int xxx,yyy;
    			scanf("%d%d",&xxx,&yyy);
    			join(xxx,yyy);
    		}
    		int ans=0;
    		for(i=1;i<=n;i++)
    		{
    			if(per[i]==i)
    			ans++;
    		}
    		printf("%d\n",ans-1);
    		//aa.clear();
    	}
    	return 0;
    }

[Submit]: http://acm.zzuli.edu.cn/zzuliacm/submitpage.php?id=1881
[Status]: http://acm.zzuli.edu.cn/zzuliacm/problemstatus.php?id=1881
[Web Board]: http://acm.zzuli.edu.cn/zzuliacm/bbs.php?pid=1881