My graph theory is poor.I had a better understanding of toposort through this problem.
Here is my code:
#include<iostream>
#include<string.h>
#define maxn 107
using namespace std;
long n,counter,path[maxn];
bool used[maxn],g[maxn][maxn];
void topo(long s)
{
for(long i=1;i<=n;i++)
if(!used[i]&&g[s][i])
topo(i);
used[s]=true;
path[counter]=s;
counter--;
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
cin>>n;
memset(g,false,sizeof(g));
for(long i=1;i<=n;i++)
{
long t;
while(cin>>t&&t)
g[i][t]=true;
}
// Input
counter=n;
memset(used,false,sizeof(used));
for(long i=1;i<=n;i++)
if(!used[i])
topo(i);
// Topo Sort
for(long i=1;i<=n;i++)
{
if(i>=2) cout<<" ";
cout<<path[i];
}
cout<<endl;
// Output
return 0;
}
posted on 2010-09-21 20:47
lee1r 閱讀(154)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論