有向图的传递闭包

2009-03-30 17:02 

#include<iostream>
#include<fstream>
using namespace std;
const int MAX = 100;
const int INFI = 100000;
struct{
      int n;
      int adjvex[MAX];
      int weight[MAX];
}Edge[MAX];
bool T[MAX][MAX];
void TransitiveClosure(int n);
int main(void){
    int n,e,a,b,v;
    int i,j;
    ifstream in("data.in");
    ofstream out("data.out");
   
    in>>n>>e;
    for(i=1;i<=n;i++)
        Edge[i].n = 0;
   
    for(i=0;i<e;i++){
        in>>a>>b;
        Edge[a].adjvex[ Edge[a].n++ ] = b;
    }
   
    TransitiveClosure(n);
   
    for(i=1;i<=n;i++)
       for(j=1;j<=n;j++)
           out<<"T["<<i<<"]["<<j<<"]:"<<T[i][j]<<endl;
                           
    system("pause");
    return 0;
}
void TransitiveClosure(int n){
     int i,j,k,u;
    
     memset(T,0,sizeof(T) );
     for(i=1;i<=n;i++)
        for(j=0;j<Edge[i].n;j++){
            u = Edge[i].adjvex[j];
            T[i][u] = true;
        }
     for(i=1;i<=n;i++)
        T[i][i] = true;
       
     for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
           for(j=1;j<=n;j++)
               T[i][j] = T[i][j]||(T[i][k]&&T[k][j]);
}