[UVA 10305]Ordering Tasks(토폴로지 정렬)

Ordering Tasks
제목 링크:http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=18723
제목 의 대의:
어떤 임 무 는 완성 해 야 하 는데,그 중 어떤 임 무 는 반드시 다른 임무 보다 먼저 완성 해 야 한다.완성 시간의 선착순 에 따라 임 무 를 정렬 하 라.
문제 풀이 방향:
토폴로지 정렬:
이 그림 의 정점 을 검색 하여 입 도 없 는 모든 점 을 출력 한 다음 이 점 과 연 결 된 점 의 입 도 를 1 로 줄 입 니 다.이 과정 을 반복 하면 된다
마찬가지 로 dfs 함수 로 토폴로지 정렬 을 완성 할 수 있 습 니 다.

int c[105], g[105][105], n, t;
int topo[105];
bool dfs(int u)
{
    c[u] = -1;
    for (int v = 1; v <= n; v++) if (g[u][v])
    {
        if (c[v] < 0) return false;
        else if (!c[v] && !dfs(v)) return false;
    }
    c[u] = 1; topo[--t] = u;
    return true;
}
bool toposort()
{
    t = n;
    mem(c, 0);
    for (int i = 1; i <= n; i++) if (!c[i])
        if (!dfs(i)) return false;
    return true;
}

c 배열,c[u]=0 으로 dfs(u)를 호출 한 적 이 없다 는 뜻 입 니 다.c[u]=1 은 방문 한 적 이 있 고 모든 자손 을 재 귀적 으로 방문 한 적 이 있 습 니 다.c[u]=-1 은 방문 하고 있 음 을 표시 합 니 다.
구현 코드:

#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int c[105], g[105][105], n, t;
int topo[105];
bool dfs(int u)
{
    c[u] = -1;
    for (int v = 1; v <= n; v++) if (g[u][v])
    {
        if (c[v] < 0) return false;
        else if (!c[v] && !dfs(v)) return false;
    }
    c[u] = 1; topo[--t] = u;
    return true;
}
bool toposort()
{
    t = n;
    mem(c, 0);
    for (int i = 1; i <= n; i++) if (!c[i])
        if (!dfs(i)) return false;
    return true;
}
int main ()
{
    int m;
    while(cin>>n>>m)
    {
        mem(g, 0);
        if (n + m == 0) break;
        int u, v;
        while(m--)
        {
            scanf("%d%d", &u, &v);
            g[u][v] = 1;
        }
        toposort();
        printf("%d", topo[0]);
        for (int i = 1; i < n; i++) printf(" %d", topo[i]);
        puts("");
    }
    return 0;
}