ZeroJudge A552: 模型

你買了一組模型，其中有 N 個零件，而零件之間有先後關係，也就是在裝上零件 y 之前，必須先將零件 x 裝上才可以，說明書上包含了 m 種 (x, y) 的關係，請問你該如何依序使用零件才能將模型完成？

範例測資

範例輸入範例輸出
本題採取循環輸入，讀至 EOF 時結束程式。
每筆測資會先有兩個數字 N 和 M 代表 N 個零件和 M 種關係，每種關係只會出現一次，N <= 100。 接下來有 M 行，每行有兩個數字 i 和 j，代表必須先將 i 裝上後，才能將 j 裝上去 (i -> j)。
本題必定有解，即不會有循環出現 (例如 1 -> 2, 2 -> 3, 3 -> 1)。		輸出一行數列共有 N 個數字，表示該依序使用哪些零件。
如果同時有多種解，請回答字典序最小的解。(有多種零件能同時選的話，要先選編號最小的)
5 4
0 4
4 3
2 1
3 2

3 2
2 0
1 0		0 4 3 2 1
1 2 0
ZeroJudge A552 範例測資

解題思路

使用 Map<int, Map<int, int>> 來紀錄每一個零件的前後有哪些零件。收完資料之後跑迴圈判斷哪一個零件沒有前面所需的零件，就宣告一個 Map<int, int> 來紀錄等一下 BFS 的起點，將其的 Map 值 ++。跑完迴圈之後就跑 BFS。

在 BFS 中，會需要一個 Map<int, int> start 來紀錄起點，並且宣告一個 Map<int, int> push 來紀錄已經使用過哪些點了。宣告一個 While 迴圈，當 start.size() == 0 時就結束迴圈，裡面要判斷 start 的第一個資料是什麼，並且將其刪除，還需判斷其的前面還有沒有需要用的零件還沒用。如果都通過的話就將其輸出。

範例程式碼－ZeroJudge A552: 模型

#include <iostream>
#include <map>
using namespace std;

map<int, map<int, int>>MAP, before;
map<int, int>walk;

void BFS(map<int, int>start) {
    map<int, int>push;
    while(start.size() > 0) {
        const auto first = *start.begin();
        start.erase(start.begin());
        const int num = first.first;
        bool ok = true;
        for (auto it:before[num]) {
            if (walk[it.first] == 0) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            push[num] = 0;
            continue;
        }
        cout << num << " ";
        walk[num]++;
        const map<int, int> mm = MAP[num];
        for (auto it:mm) {
            if (walk[it.first] == 0 && push[it.first] == 0) {
                push[it.first]++;
                start[it.first]++;
            }
        }
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    while (cin >> N >> M) {
        walk.clear();
        MAP.clear();
        before.clear();
        map<int, int>dad;
        for (int i = 0; i<M; i++) {
            int a, b;
            cin >> a >> b;
            dad[b]++;
            before[b][a]++;
            MAP[a][b]++;
        }
        map<int, int>start;
        for (int i = 0; i<N; i++) {
            if (dad[i] == 0) {
                start[i]++;
            }
        }
        BFS(start);
        cout << "\n";
    }
}

//ZeroJudge A552
//Dr. SeanXD
標籤

相關文章

發佈留言