iStrzalka

SILNIE SPÓJNE SKŁADOWE

Apr 26th, 2017
192
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.35 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. struct node{
  7.     int czasy;
  8.     vector<int> polaczenia;
  9.     int self = 100000000;
  10. };
  11.  
  12. node graph[2000];
  13. node graph2[2000];
  14.  
  15. vector <int> przechowanie;
  16.  
  17. int kolejnosc = 1;
  18.  
  19. void DFS(int START = 1, int value = -1)
  20. {
  21.     graph[START].self = value + 1;
  22.     int ile;
  23.     for(int i = 0; i < graph[START].polaczenia.size(); i++){
  24.         ile = graph[START].polaczenia[i];
  25.         if(graph[START].self + 1 < graph[ile].self){
  26.             DFS(ile,graph[START].self);
  27.         }
  28.     }
  29.     graph[START].czasy = kolejnosc;
  30.     kolejnosc++;
  31. }
  32.  
  33. void DFS2(int START = 1, int value = -1)
  34. {
  35.     graph2[START].self = value + 1;
  36.     int ile;
  37.     for(int i = 0; i < graph2[START].polaczenia.size(); i++){
  38.         ile = graph2[START].polaczenia[i];
  39.         if(graph2[ile].self == 100000000){
  40.             DFS2(ile,graph2[START].self);
  41.         }
  42.     }
  43.     przechowanie.push_back(START);
  44. }
  45.  
  46. bool pairCompare(pair<int, int> first, pair<int, int> second) {
  47.   return first.second > second.second;
  48. }
  49.  
  50.  
  51.  
  52. int main(){
  53.     int n,m,from,to;
  54.     cin >> n >> m;
  55.  
  56.     for(int i = 0;i < m; i++)
  57.     {
  58.         cin >> from >> to;
  59.         graph[from].polaczenia.push_back(to);
  60.         graph2[to].polaczenia.push_back(from);
  61.     }
  62.  
  63.     DFS();
  64.  
  65. //    for(int i = 1;i <= n; i++)
  66. //    {
  67. //        cout << graph[i].czasy << " ";
  68. //    }
  69.  
  70.     cout << endl;
  71.  
  72.     pair<int,int> tab[n];
  73.     for(int i = 0;i < n; i++)
  74.     {
  75.         tab[i] = {i+1,graph[i+1].czasy};
  76.     }
  77.     sort(tab, tab + n, pairCompare);
  78.  
  79. //    for(int i = 0;i < n; i++)
  80. //    {
  81. //        cout << tab[i].first << " " << tab[i].second << endl;
  82. //    }
  83.  
  84.     vector<vector <int> > wynik;
  85.     for(int i = 0; i < n; i++){
  86.         if(graph2[tab[i].first].self == 100000000)
  87.         {
  88.             przechowanie.clear();
  89.             DFS2(tab[i].first);
  90.             sort(przechowanie.begin(), przechowanie.end());
  91. //            for(int j = 0; j < przechowanie.size(); j++){
  92. //                cout << przechowanie[j] << " ";
  93. //            }
  94. //            cout << endl;
  95.             wynik.push_back(przechowanie);
  96.         }
  97.     }
  98.  
  99.     for(int i = 0;i < wynik.size(); i++)
  100.     {
  101.         for(int j = 0; j < wynik[i].size(); j++){
  102.             cout << wynik[i][j] << " ";
  103.         }
  104.         cout << endl;
  105.     }  
  106. }
Add Comment
Please, Sign In to add comment