无向图的连通分量

( 一 ) DFS
　　DFS的时间复杂度是O(V + E ),理论上比并查集要优。但是它的缺点是需要对整个图进行预处理，如果图进行添边操作，那么要获得新的连通分量必须对整个图重新进行DFS。所以DFS获取连通分量的方法适合用在图网络变化不怎么变化的情况。
　　它的优点是可以在常数时间内查询两个点是否可达

#include <cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN=10010;
vector<int> graph[MAXN];
vector<int> cc[MAXN];//连通分量
int vis[MAXN];
int component[MAXN];//节点所在的连通分量
int cnt;//联通分量数
void DFS(int u)
{
    vis[u]=true;
    cc[cnt].push_back(u);
    component[u]=cnt;
    int len=graph[u].size();
    for(int i=0;i<graph[u].size();i++)
    {
        int v=graph[u][i];
        if(vis[v]==0)
            DFS(v);
    }
}
void getCC(int n)
{
    memset(vis,0,sizeof(vis));
    memset(cc,0,sizeof(cc));
    memset(component,0,sizeof(component));
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            DFS(i);
            cnt++;
        }
    }
    for(int i=0;i<cnt;i++)
    {
        for(int j=0;j<cc[i].size();j++)
        {
            printf("%d ",cc[i][j]);
        }
        printf("\n");
    }
}
bool isConnected(int u,int v)//查询u,v是否连通
{
    return component[u]==component[v];
}
int main()
{
    int n,m,a,b;
    while(scanf("%d%d",&n,&m)!=EOF,n+m)
    {
        memset(graph,0,sizeof(graph));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        getCC(n);
    }
}

( 二 )并查集
　　并查集是一种动态算法，我们可以在接近常数时间内查询两个点是否连通，同时可以动态地支持添边操作。所以我们在有大量的连通性查询和插入的混合操作时，优先使用并查集。

#include <cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<map>
using namespace std;
const int MAXN=10010;
vector<int> graph[MAXN];
map<int,set<int> > cc;//连通分量
int parent[MAXN];
int grade[MAXN];
int cnt;//连通分量数
int father(int u)
{
    while(u!=parent[u])
    {
        parent[u]=parent[parent[u]];
        u=parent[u];
    }
    return u;
}
bool connect(int u,int v)//连接u,v
{
    int fu=father(u);
    int fv=father(v);
    if(fu==fv) return false;
    if(grade[fu]>grade[fv])
    {
        parent[fv]=fu;
        grade[fu]+=grade[fv];
    }
    else
    {
        parent[fu]=fv;
        grade[fv]+=grade[fu];
    }
    cnt--;
    return true;
}
bool isConnected(int u,int v)//判断u,v是否连通
{
    return father(u)==father(v);
}
void getCC(int n)
{
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
        grade[i]=1;
    }
    cnt=n;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<graph[i].size();j++)
        {
            connect(i,graph[i][j]);
        }
    }
    cc.clear();
    for(int i=1;i<=n;i++)
    {
        int fa=father(i);
        map<int,set<int> >::iterator it=cc.find(fa);
        if(it==cc.end())
        {
            set<int> tmp;
            tmp.insert(i);
            cc[fa]=tmp;
        }
        else
        {
            (it->second).insert(i);
        }
    }
    for(map<int,set<int> >::iterator it=cc.begin();it!=cc.end();it++)
    {
        for(set<int>::iterator beg=(it->second).begin();beg!=(it->second).end();beg++)
        {
            printf("%d ",*beg);
        }
        printf("\n");
    }
}
int main()
{
    int n,m,a,b;
    while(scanf("%d%d",&n,&m)!=EOF,n+m)
    {
        memset(graph,0,sizeof(graph));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        getCC(n);
    }
}