Pagini recente » Cod sursa (job #642038) | Cod sursa (job #629812) | amberheard | Cod sursa (job #2314057) | Cod sursa (job #2947472)
#include <iostream>
#include <vector>
#include <queue>
#define MAXN 50000
using namespace std;
struct node{
int inDegree;
vector <int> neighbours;
};
queue <int> q;
node graph[MAXN];
int topologicalOrder[MAXN];
int topologicalOrderSize;
void addEdge(int a, int b) {
graph[a].neighbours.push_back(b);
graph[b].inDegree++;
}
void makeTopologicalOrder(int n) {
int i, pos;
topologicalOrderSize = 0;
for ( i = 0; i < n; i++ ) {
if ( !graph[i].inDegree ) {
q.push(i);
}
}
while ( q.size() ) {
pos = q.front();
q.pop();
topologicalOrder[topologicalOrderSize] = pos;
topologicalOrderSize++;
for ( int u : graph[pos].neighbours ) {
graph[u].inDegree--;
if ( !graph[u].inDegree ) {
q.push(u);
}
}
}
}
int main() {
FILE *fin, *fout;
fin = fopen("sortaret.in", "r");
fout = fopen("sortaret.out", "w");
int n, m, a, b, i;
fscanf(fin, "%d%d", &n, &m);
for ( i = 0; i < m; i++ ) {
fscanf(fin, "%d%d", &a, &b);
a--;
b--;
addEdge(a, b);
}
makeTopologicalOrder(n);
for ( i = 0; i < topologicalOrderSize; i++ ) {
fprintf(fout, "%d ", topologicalOrder[i] + 1);
}
fprintf(fout, "\n");
fclose(fin);
fclose(fout);
return 0;
}