求连通分量【图论】

求连通分量

Time Limit:1000MS Memory Limit:65536K
Total Submit:435 Accepted:258

---

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

---

解题思路

我们老师为了我们学会灵活运用，让我们整整打了五种方法！！！
┓(;´_｀)┏ 心累
好吧，让我们进入正题，上图。。。

不知道连通分量l的请出门右转百度。。。

• 深搜（邻接矩阵）
• 深搜（邻接表）
• 广搜 （邻接矩阵）
• 广搜 （邻接表）
• 广搜 （邻接表+STL）
  对于最后一种方法，
  用法如下：
  

---

代码（五种）

求连通分量（深搜+邻接矩阵）：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,a[1000][1000],v[1000],s,t[1000],ans=-1;
void dfs(int x){
	v[x]=1;
	for(int j=1;j<=n;j++)
	{
		if(a[x][j]&&!v[j])
		{
		  s++;
		  dfs(j);
		}
	}
}
int main(){
	scanf("%d",&n);
	int x,y;
	cin>>x>>y;
	while(x)
	{
		a[x][y]=1;
		a[y][x]=1;
		cin>>x>>y;
	}
	for(int i=1;i<=n;i++)
	{
		if(!v[i])
		{
		  s=1;
		  dfs(i);
		}
		ans=max(s,ans);
    }
	cout<<ans;
}

求连通分量 （深搜+邻接表）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,v[10000],s,k[10000],ans=-1,h,t,head[10000],kk;
struct{
	int x,next;
}a[1000]; 
void bfs(int x){
	v[x]=1;
	k[1]=x;
	h=0;
	t=1;
	do
	{
		h++;
		for(int i=head[k[h]];i;i=a[i].next)
		{
			if(!v[a[i].x])
			{	
			    t++;
				++s;
				v[a[i].x]=1;
				k[t]=a[i].x;
			}	
		}
	}while(h<t);
}
void add(int x,int y){
	++kk;
	a[kk].x=y;
	a[kk].next=head[x];
	head[x]=kk;
}
int main(){
	scanf("%d",&n);
	int x,y;
	cin>>x>>y;
	while(x)
	{
		add(x,y);
		add(y,x);
		cin>>x>>y;
	}
	for(int i=1;i<=n;i++)
	{
		if(!v[i])
		{
		  s=1;
		  bfs(i);
		}
		ans=max(s,ans);
    }
	printf("%d",ans);
}

求连通分量 （广搜+邻接矩阵）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[1000][1000],v[10000],s,k[10000],ans=-1,h,t;
void bfs(int x){
	v[x]=1;
	k[1]=x;
	h=0;
	t=1;
	do
	{
		h++;
		for(int i=1;i<=n;i++)
		{
			if(a[k[h]][i]&&!v[i])
			{	
			    t++;
				s++;
				v[i]=1;
				k[t]=i;
			}
			
		}
	}while(h<t);
}
int main(){
	scanf("%d",&n);
	int x,y;
	scanf("%d%d",&x,&y);
	while(x)
	{
		a[x][y]=1;
		a[y][x]=1;
		scanf("%d%d",&x,&y);
    }
    for(int i=1;i<=n;i++)
	{
		if(!v[i])
		{
		  s=1;
		  bfs(i);
		}
		ans=max(s,ans);
    }
	printf("%d",ans);
}

求连通分量 （广搜+邻接表）

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,v[10000],s,k[10000],ans=-1,h,t,head[10000],kk;
struct{
	int x,next;
}a[1000]; 
void bfs(int x){
	queue<int>k;
	v[x]=1;
	x=k.front();
	h=0;
	t=1;
	do
	{
		k.pop();
		for(int i=head[x];i;i=a[i].next)
		{
			if(!v[a[i].x])
			{	
				++s;
				v[a[i].x]=1;
		        k.push(a[i].x);
			}	
		}
	}while(k.size());
}
void add(int x,int y){
	++kk;
	a[kk].x=y;
	a[kk].next=head[x];
	head[x]=kk;
}
int main(){
	scanf("%d",&n);
	int x,y;
	cin>>x>>y;
	while(x)
	{
		add(x,y);
		add(y,x);
		cin>>x>>y;
	}
	for(int i=1;i<=n;i++)
	{
		if(!v[i])
		{
		  s=1;
		  bfs(i);
		}
		ans=max(s,ans);
    }
	printf("%d",ans);
}

求连通分量 （广搜+邻接表STL）

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,v[10000],s,k[10000],ans=-1,h,t,head[10000],kk;
struct{
	int x,next;
}a[1000]; 
void bfs(int x){
	int xx;
	queue<int>k;
	k.push(x);
	v[x]=1;
	h=0;
	t=1;
	do
	{
	    xx=k.front();
		k.pop();
		for(int i=head[xx];i;i=a[i].next)
		{
			if(!v[a[i].x])
			{	
				++s;
				v[a[i].x]=1;
		        k.push(a[i].x);
			}	
		}
	}while(k.size());
}
void add(int x,int y){
	++kk;
	a[kk].x=y;
	a[kk].next=head[x];
	head[x]=kk;
}
int main(){
	scanf("%d",&n);
	int x,y;
	cin>>x>>y;
	while(x)
	{
		add(x,y);
		add(y,x);
		cin>>x>>y;
	}
	for(int i=1;i<=n;i++)
	{
		if(!v[i])
		{
		  s=1;
		  bfs(i);
		}
		ans=max(s,ans);
    }
	printf("%d",ans);
}