Pagini recente » Cod sursa (job #2110575) | Cod sursa (job #369784) | Cod sursa (job #2858921) | Cod sursa (job #2396342) | Cod sursa (job #2858717)
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
const int MAX_SIZE = 50005;
vector<int> graph[MAX_SIZE];
int noParents[MAX_SIZE];
void topologicalSort(int peaks) { // nu sorteaza bine
queue<int> positions;
for (int i = 1; i <= peaks; ++i) {
if (noParents[i] == 0) {
positions.push(i);
noParents[i] = 1;
}
}
while (!positions.empty()) {
int currentPeak = positions.front();
positions.pop();
for (int i = 0; i < graph[currentPeak].size(); ++i) {
--noParents[graph[currentPeak][i]];
if (noParents[graph[currentPeak][i]] == 0) {
int nextPeak = graph[currentPeak][i];
positions.push(nextPeak);
noParents[nextPeak] = 1;
}
}
fout << currentPeak << " ";
}
}
int main() {
int peaks, arches;
fin >> peaks >> arches;
for (int i = 1; i <= arches; ++i) {
int start, end;
fin >> start >> end;
if (start != end) {
graph[start].push_back(end);
++noParents[end];
}
}
topologicalSort(peaks);
return 0;
}
/*
6 6
6 3
3 4
4 2
5 2
5 1
6 1 -> 5 6 2 1 3 4 gresit
3 3
1 2
1 2
2 3 -> 1 2 3 ok
10 4
4 2
1 2
3 2
10 9 -> 1 3 4 5 6 7 8 10 2 9 ok
50000 1
499 498 -> ok (498 e dupa 499)
6 7
1 2
1 4
4 3
3 5
2 3
1 3
4 3 -> 1 6 2 4 3 5 ok
10 1
10 9 -> 1 2 3 4 5 6 7 8 10 9 ok
9 8
1 2
1 3
3 4
3 5
5 9
4 6
4 7
4 8 -> 1 2 3 4 5 6 7 8 9 ok
15 14
14 9
14 1
14 2
14 3
3 4
10 14
2 8
1 7
1 6
15 10
13 5
11 12
11 13
10 11 -> 15 10 14 11 9 1 2 3 12 13 7 6 8 4 5 OK
2 2
1 2
1 2 -> 1 2 ok
7 1
7 1 -> 2 3 4 5 6 7 1 ok
6 4
1 2
2 3
2 4
5 6 -> 1 5 2 6 3 4 ok
7 3
1 2
3 4
5 6 -> 1 3 5 7 2 4 6 ok
*/