Uva 10305. Ordering Tasks

思路：

因为是看笔记教到Kahn's Algorithm，直接练习题，所以没什麽思路不思路，直接按照算法实作。

　
　
　

程序码

#include <iostream>
#include <queue>
#define N 101
using namespace std;


int main(){
    int n, m, u, v;
    bool adj[N][N]; 
    int ref[N];  
    
    while(cin >> n >> m) {
        if (n==0 && m==0) break;
        // 初始化
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= n; j++)
                adj[i][j] = false;
        for (int i = 1; i <= n; i++) ref[i] = 0;
        
        // 输入
        for (int i = 1; i <= m; i++) {
            cin >> u >> v;
            adj[u][v] = true;
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (adj[i][j]) ref[j]++;
                
        // Kahn's Algorithm        
        deque<int> Q;
        for (int i = 1; i <= n; i++) 
            if(!ref[i]) Q.push_back(i);

        for (int i = 1; i <= n; i++) {
            if (Q.empty()) break;
            
            int s = Q.front(); Q.pop_front();
            ref[s] = -1;  
            cout << s << " "; 
     
            for (int j = 1; j <= n; j++) {
                bool flag = false;
                if(adj[s][j]) {
                    ref[j]--;
                    flag = true;
                }
                if(!ref[j] && flag) Q.push_back(j);
            }
        }
        cout << endl;
    }
}