poj 2367(拓扑排序TopSort)

题意简单，说到底就是求符合的拓扑排序。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100
using namespace std;

struct edge { int v, next; };
int g[maxn], n, list[maxn];
edge e[maxn*maxn];

bool topsortdfs( int v, edge e[], int g[], int u[], int &m )
{
    u[v] = -2;
    for ( int i = g[v]; i != -1; i = e[i].next )
        if ( u[e[i].v]==-2 ) return false;
        else if ( u[e[i].v]==-1 && !topsortdfs(e[i].v,e,g,u,m) ) return false;
    u[v] = --m;
    return true;
}

void topsort( edge e[], int g[], int n, int list[] )
{
    static int u[maxn];
    int m = n, i;
    memset(u,255,sizeof(u));
    for ( i = 0; i < n; i++ )
        if ( u[i]==-1 && !topsortdfs(i,e,g,u,m) ) return;
    for ( i = 0; i < n; i++ )
        list[u[i]] = i;
    printf( "%d", list[0]+1 );
    for ( i = 1; i < n; i++ )
        printf( " %d", list[i]+1 );
    printf( "\n" );
}

int main()
{
    int i, j, k;
    cin >> n ;
    memset(g,255,sizeof(g));
    for ( i = j = 0; i < n; i++ )
    while ( scanf("%d", &k) )
    {
        if ( k == 0 ) break;
        k--;
        e[j].v = k; e[j].next = g[i];  g[i] = j++;
    }
    topsort( e,g,n,list);
}