输入一个无向图,打印出它的所有连通分量。如
下示例,
连通分量有2个,分别为{1,2,4,5}, {3,6}
(2)输入一个有向图,打印出它的所有强连通分量。
如下示例,
强连通分量有3个,分别为{1}, {4}, {2,5,3,6}
img
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int n,m,cnt,cntb;
int f[105][105]={0},visited[105]={0}; //f邻接矩阵,a给走过的顶点做标记
int ans=0;
int a,x,y;
vector<int> edge[101];
vector<int> belong[101];
bool instack[101];
int dfn[101];
int low[101];//LOW[]作为每个点在这颗树中的,最小的子树的根,每次保证最小,like它的父亲结点的时间戳这种感觉。如果它自己的LOW[]最小,那这个点就应该从新分配,变成这个强连通分量子树的根节点。
stack<int> s;
void DFS(int s)
{
visited[s]=1; //标记已经访问过
for(int i=0;i<n;i++)
{
if(!visited[i]&&f[s][i]) //当两点连通并且此点没有被访问过
{
a++; //累计总数
visited[i]=1; //标记
cout<<i;
DFS(i); //DFS
}
}
}
void Tarjan(int u) //tarjan算法
{
++cnt;
dfn[u]=low[u]=cnt;//DFN[]作为这个点搜索的次序编号(时间戳),简单来说就是 第几个被搜索到的
s.push(u);
instack[u]=true;
for(int i=0;i<edge[u].size();++i)
{
int v=edge[u][i];
if(!dfn[v])//如果节点v未被访问过
{
Tarjan(v);// 继续向下找
low[u]=min(low[u],low[v]);
}
else if(instack[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])//如果节点u是强连通分量的根
{
++cntb;
int node;
do
{
node=s.top();
s.pop();
instack[node]=false;
belong[cntb].push_back(node);
}while(node!=u);
}
}
int main()
{
int flag=0;//为0时求有向图,为1时求无向图
cout<<"请输入要求的类型:0:有向图 1:无向图";
cin>>flag;
cout<<"请输入节点的个数n:";
cin>>n;
cout<<"请输入边的条数m:";
cin>>m;
cout<<"请输入"<<m<<"条边:\n";
if(flag==0){
for(int i=1;i<=m;++i)
{
int u,v;
cin>>u>>v;
edge[u].push_back(v);//输入边
}
Tarjan(1);
for(int i=1;i<=cntb;++i)
{
cout<<"连通分量"<<i<<" : ";
for(int j=0;j<belong[i].size();++j)
cout<<belong[i][j]<<" ";
cout<<endl;
}
}
if(flag==1){
for(int i=0;i<m;i++){
cin>>x>>y;
f[x][y]=1; f[y][x]=1; //无向图要双向处理
}
for(int i=0;i<n;i++)
{
a=0; //m记录当前顶点连通的所有顶点数
if(!visited[i]) //当此点没有被访问过
{
cout<<"连通分量"<<i;//每个连通分量的第一个输出
DFS(i);
cout<<"\n";
}
}
}
return 0;
}