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当然可以了。。
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 //题目中可能的最大点数
int DFN[M]; //深度优先搜索访问次序
int ConnectedComponetNumber=0; //有向图强连通分量个数
int Belong[M];
int Index=0;
vector <int> Edge[M]; //邻接表表示
vector <int> ConnectedComponent[M]; //获得强连通分量结果
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) //此图中点的个数，注意是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;
}
}
/*
此算法正常工作的基础是图是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;
}