ZeroJudge A552: Model

You have purchased a model kit with N parts, where parts have a specific order of assembly. This means that before assembling part y, part x must be assembled first. The instruction manual includes m relationships (x, y). How can you determine the sequence in which to use the parts to complete the model?

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
EOF Inputs:
每筆測資會先有兩個數字 N 和 M 代表 N 個零件和 M 種關係，每種關係只會出現一次，N <= 100。 接下來有 M 行，每行有兩個數字 i 和 j，代表必須先將 i 裝上後，才能將 j 裝上去 (i -> j)。
本題必定有解，即不會有循環出現 (例如 1 -> 2, 2 -> 3, 3 -> 1)。		Output a single line containing a sequence of N numbers, indicating the order in which the parts should be assembled.
If there are multiple solutions possible, please provide the lexicographically smallest solution. In cases where multiple parts can be chosen simultaneously, prioritize selecting the part with the smallest numerical identifier.
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 Sample Test Case

Thought Process

使用 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 的第一個資料是什麼，並且將其刪除，還需判斷其的前面還有沒有需要用的零件還沒用。如果都通過的話就將其輸出。

Sample Code－ZeroJudge A552: Model

#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
Tags

Related Posts

Comments