Pagini recente » Cod sursa (job #2727833) | Cod sursa (job #46829) | Cod sursa (job #992809) | Cod sursa (job #883799) | Cod sursa (job #3198034)
///topological sort based on indegree of vertex
///perform a bfs, insert to the Q every vertex with indegree 0
///while Q is not empty, extract the front vertex x, add x to solution and delete all edges (x,y)
///if indegree[y] becames 0 add y to the Q
#include <bits/stdc++.h>
using namespace std;
int N, M, nr;
vector<int>L[50002];///adjacency list
int indegree[50002];///indegree[i] = number of edges starting from i to vertices not inserted in topoSort[]
int vis[50002], topoSort[50002];
queue<int>Q;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int main(){
in >> N >> M;
for(int i = 1; i <= M; i++){
int x, y;
in >> x >> y;
L[x].push_back(y);
indegree[y] = indegree[y] + 1;
}
for(int i = 1; i <= N; i++) if(indegree[i] == 0) Q.push(i);///insert all vertices with 0 indegree
nr = 0;
while(Q.empty() == false){
int x = Q.front();
Q.pop();
nr = nr + 1;
topoSort[nr] = x;
for(int i = 0; i < L[x].size(); i++){
int j = L[x][i];
indegree[j] = indegree[j] - 1;///remove edge x --> j
if(indegree[j] == 0) Q.push(j);///add to queue
}
}
for(int i = 1; i <= N; i++) out << topoSort[i] << " ";
return 0;
}