UVa10305

Posted on Edited on In , Views:

題目:
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1246

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
 
// DFS version

vector<vector<int>> arr(105);
bool visited[105];
stack<int> ans;

void dfs(int num){
    visited[num] = true;
    
    for(auto successor : arr[num]){
        if(!visited[successor]){
            dfs(successor);
        }
    }
    ans.push(num);
}

int main(){
    int m, n;
    while(cin >> m >> n && m != 0){
        arr.assign(105, vector<int>());
        memset(visited, false, sizeof(visited));

        int i, j;
        while(n--){
            cin >> i >> j;
            arr[i].push_back(j); // i precedes j
        }

        for(int i = 1; i <= m; ++i){
            if(!visited[i]) dfs(i);
        }

        bool flag = true;
        while(!ans.empty()){
            if(!flag) cout << ' ';
            flag = false;
            cout << ans.top();
            ans.pop();
        }
        cout << '\n';
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// topologic version
#include <bits/stdc++.h>
using namespace std;

int main(){
    int m, n;
    while(cin >> m >> n && m != 0){
        vector<vector<int>> arr(m+5);
        vector<int> inDegree(m+5, 0);

        int x, y;
        while(n--){
            cin >> x >> y;
            arr[x].push_back(y); // x precedes y
            inDegree[y]++; // indegree of y ++
        }

        queue<int> q; // free tasks
        for(int i=1; i<=m; ++i){
            if(inDegree[i] == 0) q.push(i);
        }

        vector<int> ans;
        while(!q.empty()){
            int curr = q.front();
            q.pop();
            ans.push_back(curr);

            for(int successor : arr[curr]){ // find successors
                inDegree[successor]--;

                if(inDegree[successor] == 0) q.push(successor);
            }
        }

        bool flag = true;
        for(auto num : ans){
            if(!flag) cout << ' ';
            flag = false;
            cout << num;
        }
        cout << '\n';
    }
    return 0;
}