Mai intai trebuie sa te autentifici.
Cod sursa(job #1543138)
| Utilizator | Data | 5 decembrie 2015 23:21:42 | |
|---|---|---|---|
| Problema | Sortare topologica | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.83 kb |
#include<iostream>
#include <bitset>
#include <vector>
#define DIM 65536
using namespace std;
int n,m,x,y, Rank[DIM];
vector <int> Edges[DIM], Stack; bitset <DIM> Marked;
void DFS (int node) {
Marked[node] = 1;
vector <int> :: iterator it;
for (it = Edges[node].begin(); it != Edges[node].end(); it ++) {
int nextNode = *it;
if (!Marked[nextNode])
DFS (nextNode);
}
Stack.push_back(node);
return;
}
int main () {
cin>>n>>m;
for (int i = 1; i <= m; i ++) {
cin>>x>>y;
Edges[x].push_back(y);
Rank[y] ++;
}
for (int i = 1; i <= n; i ++)
if (!Rank[i]) DFS (i);
vector <int> :: reverse_iterator it;
for (it = Stack.rbegin(); it != Stack.rend(); it ++)
cout<<*it<<" ";
return 0;
}
