题目描述

该题的目的是要你统计图的连通分支数。

输入描述:

每个输入文件包含若干行，每行两个整数i,j，表示节点i和j之间存在一条边。

输出描述:

输出每个图的联通分支数。

输入

1 4
4 3
5 5

输出

2

版本1

深搜，还可以用并查集做

#include<bits/stdc++.h>
using namespace std;
const int maxn=500001;
int vis[maxn];
vector<int> G[maxn];
void dfs(int r){
	vis[r]=1;
	for(int i=0;i<G[r].size();i++){
		int v = G[r][i];
		if(vis[v]) continue;
		dfs(v);
	}
}
int main(){
	int u,v; 
	fill(vis,vis+maxn,1);
	while(cin>>u>>v){
		G[u].push_back(v);
		G[v].push_back(u);
		vis[u]=vis[v]=0;
	}
	int cnt=0;
	for(int i=0;i<maxn;i++){
		if(vis[i]==0){
			dfs(i);
			cnt++;
		}
	}
	cout<<cnt<<endl;
	return 0;
}