求連通分量

Time Limit:1000MS Memory Limit:65536K
Total Submit:481 Accepted:290

Description

求一個圖的連通分量

Input

n 頂點數(<=100)
邊

Output

連通分量

Sample Input

8
6 3
1 2
2 5
5 4
4 1
8 7
0 0

Sample Output

4

思路

圖論基本例題，連通分量指的是最大連通數，這里提供五種方法：

鄰接矩陣：

a[x][y]=1表示x到y存在路徑，無向圖所以a[y][x]也要標記為1，

1.鄰接矩陣dfs

鄰接矩陣存盤路徑，列舉每個沒訪問過的點開始 dfs，求出連通分量，

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,x,y,a[101][101],b[101],t,head,tail,c[201],w,s,ans=0;
void in(){
	cin>>n;
	do{
		cin>>x>>y;
		if(!x) break;
		a[x][y]=1;
		a[y][x]=1;
		//鄰接矩陣標記路徑
	}while(1);
}
int dfs(int f){
	for(int i=1;i<=n;i++){
	//列舉每個點，若當前的點與該點存在路徑且沒訪問過，則往該點搜索
		if(a[f][i]&&!b[i]){
			s++;
			b[i]=1;
			dfs(i);
		}
	}return s;
}
int main(){
	in();
	for(int i=1;i<=n;i++){
		s=1;
		if(!b[i]){
			b[i]=1;
			ans=max(ans,dfs(i));
		}
	}cout<<ans;
}

2.鄰接矩陣bfs

鄰接矩陣存盤路徑，列舉每個沒訪問過的點開始 bfs，求出連通分量，

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,x,y,a[101][101],b[101],t,head,tail,c[201],w,s,ans;
void in(){
	cin>>n;
	do{
		cin>>x>>y;
		if(!x) break;
		a[x][y]=1;
		a[y][x]=1;
		//鄰接矩陣標記路徑
	}while(1);
}
int bfs(int f){
	head=0;tail=1;
	//head:隊首， tail:隊尾
	c[1]=f;
	do{
		head++;w=c[head];
		for(int i=1;i<=n;i++){
		//列舉每個點，若當前的點與該點存在路徑且沒訪問過，則將該點加入佇列
			if(a[w][i]&&!b[i]){
				b[i]=1;
				c[++tail]=i;
				s++;
			}
		}
	}while(head!=tail);
	return s;
}
int main(){
	in();
	for(int i=1;i<=n;i++){
		s=1;
		if(!b[i]){
			b[i]=1;
			ans=max(ans,bfs(i));
		}
	}cout<<ans;
}

鄰接表：

cin>>x>>y;

e[++l].y=y;e[l].nt=h[x];h[x]=l;
e[++l].y=x;e[l].nt=h[y];h[y]=l;
// 無向圖，所以路徑反過來也要存盤

3.鄰接表dfs

鄰接表存盤路徑，列舉每個沒訪問過的點開始 dfs，求出連通分量，
dfs:列舉每個當前點能通且沒訪問過的點搜索下去，

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,x,y,b[101],t,head,tail,c[201],w,s,ans=0,l,h[10001];
struct haha{
	int y,nt;
}e[11000];
void in(){
	cin>>n;
	do{
		cin>>x>>y;
		if(!x) break;
		e[++l].y=y;e[l].nt=h[x];h[x]=l;
		e[++l].y=x;e[l].nt=h[y];h[y]=l;
		//鄰接表存盤路徑
	}while(1);
}
int dfs(int f){
	for(int i=h[f];i;i=e[i].nt){
	//列舉每個當前點能通且沒訪問過的點搜索下去
		if(!b[e[i].y]){
			b[e[i].y]=1;
			s++;
			dfs(e[i].y);
		}
	}return s;
}
int main(){
	in();
	for(int i=1;i<=n;i++){
		s=1;
		if(!b[i]){
			b[i]=1;
			ans=max(ans,dfs(i));
		}
	}cout<<ans;
}

4.鄰接表bfs

跟dfs一樣，列舉每個沒訪問過的點開始 bfs，列舉每個當前點能通且沒訪問過的點加入佇列，求出連通分量，

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,x,y,b[101],t,head,tail,c[201],w,s,ans=0,l,h[10001];
struct haha{
	int y,nt;
}e[11000];
void in(){
	cin>>n;
	do{
		cin>>x>>y;
		if(!x) break;
		e[++l].y=y;e[l].nt=h[x];h[x]=l;
		e[++l].y=x;e[l].nt=h[y];h[y]=l;
	}while(1);
}
int bfs(int f){
	head=0;tail=1;
	c[1]=f;
	do{
		head++;w=c[head];
		for(int i=h[w];i;i=e[i].nt){
			if(!b[e[i].y]){
			//列舉每個當前點能通且沒訪問過的點加入佇列
				b[e[i].y]=1;
				c[++tail]=e[i].y;
				s++;
			}
		}
	}while(head!=tail);
	return s;
}
int main(){
	in();
	for(int i=1;i<=n;i++){
		s=1;
		if(!b[i]){
			b[i]=1;
			ans=max(ans,bfs(i));
		}
	}cout<<ans;
}

5.鄰接表bfs+STL

使用queue自帶佇列

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,x,y,b[101],t,head,tail,c[201],w,s,ans=0,l,h[10001];
struct haha{
	int y,nt;
}e[11000];
void in(){
	cin>>n;
	do{
		cin>>x>>y;
		if(!x) break;
		e[++l].y=y;e[l].nt=h[x];h[x]=l;
		e[++l].y=x;e[l].nt=h[y];h[y]=l;
	}while(1);
}
int bfs(int f){
	queue<int> c;//定義佇列
	c.push(f);//推入f
	do{
		w=c.front();//取隊首
		for(int i=h[w];i;i=e[i].nt){
			if(!b[e[i].y]){
				b[e[i].y]=1;
				c.push(e[i].y);
				s++;
			}
		}c.pop();//彈出隊首
	}while(!c.empty());//若佇列非空，則繼續回圈
	return s;
}
int main(){
	in();
	for(int i=1;i<=n;i++){
		s=1;
		if(!b[i]){
			b[i]=1;
			ans=max(ans,bfs(i));
		}
	}cout<<ans;
}