Chinaunix首页 | 论坛 | 博客
  • 博客访问: 38467
  • 博文数量: 64
  • 博客积分: 2640
  • 博客等级: 少校
  • 技术积分: 670
  • 用 户 组: 普通用户
  • 注册时间: 2010-01-26 13:15
文章分类
文章存档

2010年(64)

我的朋友
最近访客

分类: 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]);
         }
}


阅读(262) | 评论(0) | 转发(0) |
0

上一篇:heapsort

下一篇:【转】算定积分的程序

给主人留下些什么吧!~~