folstfolst
全部博文(64)
2010年(64)
Phyllis6
分类: C/C++
2010-01-26 14:21:12
#include<iostream> using namespace std; const int MAX = 100; #define BLACK 1 #define WHITE 0 #define GRAY -1 struct{ int n; int adjvex[MAX]; }Edge[MAX],GT_Edge[MAX]; int List[MAX],k; int color[MAX]; int SCC[MAX]; void DFS(int cur); void StronglyConnectedComponent(int n); void Calc_GT(int n); void GT_DFS(int cur); int main(void){ int n,e,a,b; int i,j; cout<<"Input vexnum&&edgenum:"; cin>>n>>e; for(i=1;i<=n;i++) Edge[i].n = 0; cout<<"Input the edges:"; for(i=0;i<e;i++){ cin>>a>>b; Edge[a].adjvex[ Edge[a].n++ ] = b; } StronglyConnectedComponent(n); for(i=1;i<=n;i++) cout<<"SCC["<<i<<"]:"<<SCC[i]<<"\t"; cout<<endl; system("pause"); return 0; } void DFS(int cur){ int i,next; color[cur] = GRAY; for(i=0;i<Edge[cur].n;i++){ next = Edge[cur].adjvex[i]; if(color[next]==WHITE) DFS(next); } color[cur] = BLACK; List[--k] = cur; } void Calc_GT(int n){ int i,j,u; for(i=1;i<=n;i++) GT_Edge[i].n = 0; for(i=1;i<=n;i++) for(j=0;j<Edge[i].n;j++){ u = Edge[i].adjvex[j]; GT_Edge[u].adjvex[GT_Edge[u].n++] = i; } } void GT_DFS(int cur){ int i,j,u; SCC[cur] = k; color[cur] = GRAY; for(i=0;i<GT_Edge[cur].n;i++){ u = GT_Edge[cur].adjvex[i]; if(color[u]==WHITE) GT_DFS(u); } color[cur] = BLACK; } void StronglyConnectedComponent(int n){ int i; memset(color,0,sizeof(color) ); k = n; for(i=1;i<=n;i++) if(color[i]==WHITE) DFS(i); Calc_GT(n); memset(color,0,sizeof(color) ); k = 0; for(i=0;i<n;i++) if(color[List[i] ]==WHITE){ k++; GT_DFS(List[i]); } }
上一篇:heapsort
下一篇:【转】算定积分的程序
登录 注册