Pagini recente » Cod sursa (job #2663847) | Cod sursa (job #2649979) | Cod sursa (job #2332070) | Cod sursa (job #1811110) | Cod sursa (job #2657896)
#include<bits/stdc++.h>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector <int> AdjList[50005]; // Step 1: Initializing AdjList
queue <int> q;
bool repetare(int x,int y)
{ for(int i=0;i<AdjList[x].size();i++)
if(AdjList[x][i]==y)
return 0;
return 1;
}
int main()
{
int x, y, e,v;
in >> v >> e; // Number of vertices and edges
vector<int> indegree(v+1, 0); // Step 1: Initializing indegrees to 0
for(int i=0; i < e; i++)
{
in >> x >> y;
if(repetare(x,y))
{indegree[y]++; // Incrementing indegree
AdjList[x].push_back(y);} // Add the edge x -> y to adjacency list
}
for(int i = 1; i <= v; i++)
if(indegree[i]==0) q.push(i); // Step 2: Add all indegree 0 nodes to queue
while(!q.empty()) // Step 3: Remove vertex from queue
{
for(int x=0;x<AdjList[q.front()].size();x++)
{ int y=AdjList[q.front()][x];
indegree[y]--; // Step 3.2 Reduce indegree of adjacent node
if(indegree[y]==0) q.push(y); // Step 3.3 Push adjacent node with indegree 0
}
out << q.front()<<" ";
q.pop();
} // Step 4: Repeat until queue is empty
return 0;
}