In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components. A graph that is itself connected has exactly one connected component, consisting of the whole graph.
A graph with three connected components.
顯然DFS就足夠判斷了。。BFS當(dāng)然可以了。。
Code：
#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "iostream"
#include "sstream"
#include "set"
#include "queue"
#include "stack"
#include "fstream"
#include "strstream"
using namespace std;
#define M 5000 //題目中可能的最大點(diǎn)數(shù)
int DFN[M]; //深度優(yōu)先搜索訪問(wèn)次序
int ConnectedComponetNumber=0; //有向圖強(qiáng)連通分量個(gè)數(shù)
int Belong[M];
int Index=0;
vector <int> Edge[M]; //鄰接表表示
vector <int> ConnectedComponent[M]; //獲得強(qiáng)連通分量結(jié)果
void DFS(int i)
{
DFN[i]=Index++;
Belong[i]=ConnectedComponetNumber;
ConnectedComponent[ConnectedComponetNumber].push_back(i);
for (int e=0;e<Edge[i].size();e++)
{
int j=Edge[i][e];
if (DFN[j]==-1)
DFS(j);
}
}
void solve(int N) //此圖中點(diǎn)的個(gè)數(shù)，注意是0-indexed！
{
memset(DFN,-1,sizeof(DFN));
memset(Belong,0,sizeof(Belong));
for(int i=0;i<N;i++)
if(DFN[i]==-1)
ConnectedComponetNumber++,DFS(i);
}
void reshape(int N)
{
cout<<ConnectedComponetNumber<<endl;
for(int i=0;i<N;i++)
cout<<Belong[i]<<" ";
cout<<endl;
for(int i=0;i<N;i++)
cout<<DFN[i]<<" ";
cout<<endl;
for(int i=1;i<=ConnectedComponetNumber;i++)
{
for(int j=0;j<ConnectedComponent[i].size();j++)
cout<<ConnectedComponent[i][j]<<" ";
cout<<endl;
}
}
/*
此算法正常工作的基礎(chǔ)是圖是0-indexed的。
*/
int main()
{
Edge[0].push_back(1);
Edge[1].push_back(0),Edge[1].push_back(2);
Edge[2].push_back(1);
int N=6;
solve(N);
reshape(N);
return 0;
}