fork download
copy 
  1. /*
  2.   Zenit CK 2011/2012, uloha i)
  3.   Riesenie by Zemco
  4.  
  5.   Na uplne pochopenie tohto riesenia si asi chcete zistit, co to je topologicke usporiadanie 
  6.   orientovaneho grafu.   Uvazujeme nachvilu len graf z orientovanych hran (odmyslime
  7.   si tie dvojsmerne, ktore mame rusit). Oznacme tento graf G'. Platia nasledovne tvrdenia:
  8.  
  9.   1) Ak sa v grafe G' nenachadza cyklus, existuje topologicke usporiadanie grafu G'
  10.   2) Ak existuje topologicke usporiadanie grafu G', potom vieme doplnit dvojsmerne hrany s 
  11.   jednym zrusenym smerom tak, aby nevznikol cyklus. Odpoved je teda 'existuje'
  12.   3) Ak sa v grafe G' nachadza cyklus, odpoved je urcite 'neexistuje'
  13.  
  14.   Zaver: treba skontrolovat existenciu cyklu. moj kod ale priamo pre
  15.   nazornost skusa zostrojovat toplogicke usporiadanie (co je ekvivalentne). 
  16.    */
  17. #include<cstdio>
  18. #include<vector>
  19. #include<queue>
  20. #include<iostream>
  21. #include<cstdlib>
  22. using namespace std;
  23.  
  24. #define FOR(i,N) for(int i=0;i<(int)N;i++)
  25.  
  26. int N,M,K,TT;
  27. vector<vector<int> > G;
  28. //indegree, vstupny stupen
  29. vector<int> ID;
  30.  
  31. //vratu true, ak existuje topologicke usporiadanie grafu.
  32. bool top_sort(vector<vector<int> > &G, vector<int> &ID){
  33.   //fronta s vrcholmi, ktore mozeme zaradit to top. usporiadania a spracovat
  34.   queue<int> Q;
  35.   int N = G.size();
  36.   int processed = 0;
  37.   FOR(i,N) if (ID[i] == 0) Q.push(i);
  38.   while(!Q.empty()){
  39.     int p = Q.front();
  40.     Q.pop();
  41.     processed++;
  42.     FOR(i,G[p].size()){
  43.       //oslabime indegree o jedna
  44.       ID[G[p][i]]--;
  45.       //ak uz nic nespracovane do neho nesmeruje, mozeme spracovat aj jeho
  46.       if (ID[G[p][i]] == 0) Q.push(G[p][i]);
  47.     }
  48.   }
  49.   return processed == N;
  50. }
  51.  
  52. int main(){
  53.   scanf("%d ",&TT);
  54.   FOR(tt,TT){
  55.     scanf("%d %d %d ",&N,&M,&K);
  56.     G = vector<vector<int> >(N,vector<int>(0));
  57.     ID = vector<int>(N,0);
  58.     FOR(i,M){
  59.       int x,y;
  60.       scanf("%d %d ",&x,&y);
  61.       x--; y--;
  62.       G[x].push_back(y);
  63.       ID[y]++;
  64.      }
  65.     FOR(i,K){
  66.       int x,y;
  67.       scanf("%d %d ",&x,&y);
  68.     }
  69.  
  70.     bool ok = top_sort(G,ID);
  71.     if (ok) printf("existuje\n");
  72.     else printf("neexistuje\n");
  73.   }
  74. }
Success #stdin #stdout 0.02s 2728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7ahuG
language:
C++ (gcc 8.3)
created:
12 years 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!