Guest User

Untitled

a guest
May 6th, 2016
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. #define MAXN 100
  6.  
  7. vector<int> v[301];
  8. int i1,i2;
  9. int vis[301];
  10. vector<int>wynik;
  11. int N;
  12. int max_wierzcholek;
  13. int wch[10000];
  14.  
  15.  
  16. void wczytaj_graf()
  17. {
  18. int i1, i2;
  19. for(int i=0;i<N;i++)
  20. {
  21. cin >> i1 >> i2;
  22. v[i1].push_back(i2);
  23. wch[i2]++;
  24. max_wierzcholek=max(max_wierzcholek,max(i1,i2));
  25.  
  26. }
  27. }
  28.  
  29.  
  30. void dfs(int x)
  31. {
  32. for(int i=0;i<v[x].size();i++)
  33. {
  34. int s=v[x][i];
  35. if(vis[s]==0)
  36. {
  37. vis[s]=1;
  38. dfs(s);
  39. }
  40. }
  41. wynik.push_back(x);
  42. }
  43. int main()
  44. {
  45. for(int i=0;i<301;i++)
  46. {
  47. wch[i]=0;
  48. }
  49. int licz=0, licz2=0;
  50. cin >> N;
  51. wczytaj_graf();
  52.  
  53. for(int i=1;i<=max_wierzcholek;i++)
  54. if(wch[i]==0) licz++;
  55. for(int i=1;i<=max_wierzcholek;i++)
  56. {
  57. if(v[i].empty()) licz2++;
  58. }
  59. if(licz!=1 || licz2!=1)
  60. {
  61. cout << "NIE";
  62. return 0;
  63. }
  64.  
  65. for(int i=1;i<=max_wierzcholek;i++)
  66. vis[i]=0;
  67. for(int i=1;i<=max_wierzcholek;i++)
  68. {
  69. if(vis[i]==0)
  70. {
  71. vis[i]=1;
  72. dfs(i);
  73. }
  74.  
  75. }
  76.  
  77. for(int i=wynik.size()-1;i>=0;i--) cout << wynik[i] << endl;
  78. return 0;
  79. }
Add Comment
Please, Sign In to add comment