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: Each test case begins with two numbers, N and M, where N represents the number of parts and M represents the number of dependencies. Each dependency (i, j) indicates that part i must be assembled before part j can be assembled (i -> j). Each relationship appears exactly once. N is limited to 100. Following this, there are M lines, each containing two numbers i and j. This problem is guaranteed to have a solution, meaning there won't be any cycles (e.g., 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 |
Thought Process
Use Map<int, Map> to record which parts each part depends on. After collecting the data, iterate through a loop to determine which part does not depend on any other parts. Then declare a Map to record the starting points for BFS, incrementing its Map value++. After finishing the loop, run BFS.
In BFS (Breadth-First Search), you need a Map start to record the starting points and declare a Map push to track which points have already been used. You'll use a while loop that continues until start.size() == 0. Inside the loop, you'll check what the first data in start is, delete it, and then determine if all the required components before it have been used. If they have, you'll output it.
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