#include <iostream>//有向图的强连通分量//翻转边集 深度优先遍历using namespace std;typedef struct{ int vexs[10]; int edges[10][10]; int n; int e;}MGraph;void CreateGraphM(MGraph *G){ int N1,N2; int i,j,k; printf("Enter the number of vertexs and edges: \n"); scanf("%d %d",&G->n,&G->e); k=G->n; for(i=0;i<k;i++) scanf("%d",&G->vexs[i]); for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) G->edges[i][j]=0; cout<<"EDGES: "<<endl; for(k=0;k<G->e;k++){ cin>>N1>>N2; G->edges[N1-1][N2-1]=1; } return;}typedef struct{ int visited[10]; int finishing_time[10]; int discovery_time[10]; int times;}DFS_DATA;MGraph TransGraph(MGraph *G){ int i; int j; MGraph TMP; TMP.n = G->n; TMP.e = G->e; for(i=0;i<G->n;i++) TMP.vexs[i]=G->vexs[i]; for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) TMP.edges[i][j]=0; for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) if(G->edges[i][j]==1){ TMP.edges[j][i]=1; } return TMP;}void DFSM(MGraph *G,int index,DFS_DATA *DATA){ DATA->times++; DATA->discovery_time[index]=DATA->times; DATA->visited[index]=1; cout<<G->vexs[index]<<" "; for(int i=0;i<G->n;i++) if(G->edges[index][i]==1 && DATA->visited[i]==0){ DFSM(G,i,DATA); } DATA->finishing_time[index]=DATA->times; DATA->times++;}void Strongly_Components(MGraph *G){ DFS_DATA *DATA = new DFS_DATA; MGraph TMP; int NUMBER=1; for(int i=0;i<G->n;i++){ DATA->visited[i]=0; } for(int i=0;i<G->n;i++){ DATA->finishing_time[i]=0; DATA->discovery_time[i]=0; } DATA->times=0; TMP=TransGraph(G); for(int i=0;i<G->n;i++) if(DATA->visited[i]==0){ cout<<"Strong Component "<<NUMBER<<": "; DFSM(&TMP,i,DATA); NUMBER++; cout<<endl; } return;}int main(){ MGraph *G = new MGraph; CreateGraphM(G); Strongly_Components(G); delete G; return 0;}
这算法很简单 就是先翻转G 就是所有边的方向倒转
然后用DFS看图能分成几个部分, 这几个部分就是强连通分量
