Cod sursa(job #2657814)

Utilizator patriciaxdBraica Patricia patriciaxd Data 12 octombrie 2020 11:10:51
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#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, 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;
}