Pagini recente » Cod sursa (job #809936) | Cod sursa (job #1898739) | Cod sursa (job #752862) | Cod sursa (job #2677958) | Cod sursa (job #2857138)
#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;
const int MAX_SUM = 1000000001;
vector<int> graph[MAX_SIZE], graph2[MAX_SIZE];
vector<int> costs[MAX_SIZE];
//int costs[MAX_SIZE][MAX_SIZE];
int distances[MAX_SIZE];
void findMinimumCosts(int peaks) {
queue<int> positions;
for (int i = 1; i <= peaks; ++i) {
if (graph2[i].size() == 0) {
positions.push(i);
}
}
while (!positions.empty()) {
int currentPeak = positions.front();
positions.pop();
for (int i = 0; i < graph[currentPeak].size(); ++i) {
positions.push(graph[currentPeak][i]);
}
fout << currentPeak << " ";
}
}
int main() {
int peaks, arches;
fin >> peaks >> arches;
for (int i = 1; i <= arches; ++i) {
int start, end;
fin >> start >> end;
graph[start].push_back(end);
graph2[end].push_back(start);
}
findMinimumCosts(peaks);
return 0;
}
/*
1 ≤ N ≤ 50 000
1 ≤ M ≤ 250 000
Lungimile arcelor sunt numere naturale cel mult egale cu 20 000.
Pot exista arce de lungime 0
Nu exista un arc de la un nod la acelasi nod.
Daca nu exista drum de la nodul 1 la un nod i, se considera ca lungimea minima este 0.
Arcele date in fisierul de intrare nu se repeta.
50000 7
1 2 1
2 3 2
3 4 3
4 5 1
1 5 700
2 5 100
3 5 30 -> 1 3 5 7 + multe 0-uri
5 7
1 2 1
2 3 2
3 4 3
4 5 1
1 5 700
2 5 100
3 5 30 -> 1 3 6 7
5 3
1 5 2
1 4 5
5 4 1 -> 0 0 3 2
5 3
1 5 2
1 4 3
5 4 1 -> 0 0 3 2
3 1
1 2 1 -> 1 0
4 4
1 2 1
1 3 2
3 4 1
2 4 1 -> 1 2 2
5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6 -> 1 3 2 5
*/