2013年 ACM 有为杯 Problem I —AG）

有为杯 Problem I

DAG 有向无环图

A direct acylic graph(DAG)，is a directed graph with no directed cycles . That is ,it is formed by a collection of vertion of vertices and directed edges , each edge

connecting one vertex to another,such that there is no way to way start at some vertex v and follow a squence of edges that eventually loops back to v again.

Given a DAG，output how many vertices each vetex can reach (including itself).

这是我根据题目写的算法，请各位品评、品评

#include<iostream>
#define g 10000
using namespace std;
int istr[g];//遍历过的点做标志
int a[g][g];

//深度遍历
void deeptaG(int k,int n){
int i;
istr[n]=1;
for(i=0;i<k;i++){
if(a[n][i]!=0 && !istr[i]){
deeptaG(k,i);
}
}
}

int main(){

int o,p,i,k,j;
int n,l;
cin>>k>>l;
while(l--){
cin>>o>>p;
a[o][p]=1;}

for (i=0;i<k;i++){
for (int h=0;h<k;h++)
{ istr[h]=0; }
deeptaG(k,i);
j=0;
for(int u=0;u<k;u++)
if(istr[u]==1){++j;}
cout<<j<<endl;
}
return 0;
}