fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. vector<int>id;
  5. vector<vector<int>> graph;
  6. vector<vector<int>>revGraph;
  7. stack<int >st;
  8. int comonent=0;
  9. vector<int>vis;
  10.  
  11. void dfs(int u)
  12. {
  13.     vis[u]=1;
  14.     for(auto v:graph[u])
  15. {
  16.     if(vis[v]==0)
  17.         {
  18.             dfs(v);
  19.         }
  20.     }
  21.     st.push(u);
  22. }
  23. void dfs2(int u,vector<int  > scc)
  24. {
  25.     vis[u]=1;
  26.  
  27.     scc.push_back(u);
  28.     for(auto v:revGraph[u])
  29.     {
  30.         if(vis[v]==0)
  31.         {
  32.             dfs2(u,scc);
  33.         }
  34.     }
  35. }
  36.  
  37. int main()
  38. {
  39.     cin>>n>>m;
  40.    // id.assign(n);
  41.     for(int i=0; i<n; i++)
  42.     {
  43.         int a;
  44.         cin>>a;
  45.         id.push_back(a);
  46.     }
  47.     graph.assign(n+1, {});
  48.     revGraph.assign(n+1, {});
  49.     vis.assign(n+1,0);
  50.     vector<int>indegree(n+1,0);
  51.  
  52.  
  53.     for(int i=0; i<m; i++)
  54.     {
  55.         int u,v;
  56.         cin>>u>>v;
  57.         graph[u].push_back(v);
  58.         indegree[v]++;
  59.         revGraph[v].push_back(u);
  60.     }
  61. //    for(int i=1; i<=n; i++)
  62. //    {
  63. //        if(vis[i]==0) dfs(i);
  64. //    }
  65. //    fill(vis.begin(),vis.end(),0);
  66. //    for(int i=1; i<=n; i++)
  67. //    {
  68. //        vector<int>scc;
  69. //        if(vis[i]==0) dfs2(i,scc);
  70. //    }
  71.  
  72.     queue<int>q;
  73.     vector<int>order;
  74.    vector<vector<int>>serial;
  75.  
  76.     for(int i=1; i<=n; i++)
  77.     {
  78.         if(indegree[i]==0) q.push(i);
  79.     }
  80.     while(!q.empty())
  81.     {
  82.         int u = q.front();
  83.         q.pop();
  84.         order.push_back(u);
  85.         for(auto v:graph[u])
  86.         {
  87.             indegree[v]--;
  88.             if(indegree[v]==0)q.push(v);
  89.  
  90.         }
  91.  
  92.     }
  93.  
  94.     if(order.size()==n){
  95.     for(auto v:order){
  96.         cout<<v<<" ";
  97.  
  98.     }}
  99.     else{
  100.         cout<<-1;
  101.     }
  102. }
  103.  
  104.  
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CoiNFC
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!