统计连通数数量做法

解题思路:
需要修的最少路径数量是连通数量减一
注意事项:

参考代码:

#include<iostream> 
#include<cstring>
using namespace std;
const int N=2010;
bool flag[N];
int g[N][N];
int n,m;
void dfs(int u)
{
	flag[u]=true;
	for(int j=1;j<=n;j++)
	{
		if(g[u][j]&&!flag[j])
    	dfs(j);
    }
}
int main()
{
	cin>>n;
	while(n) 
	{
		cin>>m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		g[a][b]=g[b][a]=1;
	}
	int num=0;
	for(int i=1;i<=n;i++)
	{
		if(!flag[i]) 
		{
			dfs(i);
			num++;
		}
	}
	if(num>0)
	cout<<num-1<<endl;
	else cout<<0<<endl; 
	memset(g,0,sizeof(g));
	for(int i=1;i<=n;i++) flag[i]=false;
	cin>>n;
	}
	return 0;
}