Facebook
From Cobalt Cassowary, 7 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 290
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <list>
  5. using namespace std;
  6. list <int> *graf;
  7. int *color, *where_now;
  8. bool cykl;
  9. vector <int> topsort;
  10.  
  11. void dfs(int x){
  12.       if(cykl == false){
  13.               color[x] = 1;
  14.  
  15.               for(list<int>::iterator K = graf[x].begin(); K != graf[x].end(); K++){
  16.                       if(color[*K] == 0){
  17.                               dfs(*K);
  18.                       }
  19.                       else{
  20.                               if(color[*K] == 1){
  21.                                       cykl = true;
  22.                                       return;
  23.                               }
  24.                       }
  25.               }
  26.  
  27.               topsort.push_back(x);
  28.               color[x] = 2;
  29.       }
  30. }
  31.  
  32. void dfsMAX(int V){
  33.       cykl = false;
  34.  
  35.       topsort.clear();
  36.  
  37.       for(int i = 1; i <= V; i++){
  38.               if(color[i] != 2){
  39.                       dfs(i);
  40.               }
  41.               if(cykl == true)
  42.                       break;
  43.       }
  44. }
  45.  
  46. int main(){
  47.       ios_base::sync_with_stdio(false);
  48.  
  49.       int z;
  50.       cin >> z;
  51.  
  52.       while(z--){
  53.               int V, E;
  54.               cin >> V >> E;
  55.  
  56.               graf = new list<int>[V + 1];
  57.               color = new int[V + 1];
  58.               where_now = new int[V + 1];
  59.  
  60.               for(int i = 1; i <= V; i++){
  61.                       color[i] = 0;
  62.                       where_now[i] = 0;
  63.               }
  64.  
  65.               for(int i = 1; i <= E; i++){
  66.                       int a, b; char c;
  67.                       cin >> a >> c >> b;
  68.                       graf[a].push_back(b);
  69.               }
  70.               dfsMAX(V);
  71.  
  72.               if(cykl == true){
  73.                       cout << "NIE" << endl;
  74.               }else{
  75.                       where_now[topsort[topsort.size() - 1]] = 1;
  76.  
  77.                       int maks = 1;
  78.  
  79.                       for(list<int>::iterator K = graf[topsort[topsort.size() - 1]].begin(); K != graf[topsort[topsort.size() - 1]].end(); K++){
  80.                               where_now[*K] = max(where_now[*K], where_now[topsort[topsort.size() - 1]] + 1);
  81.                               maks = max(maks, where_now[*K]);
  82.                       }
  83.  
  84.                       for(int i = topsort.size() - 2; i >= 0; i--){
  85.                               if(where_now[topsort[i]] == 0){
  86.                                       where_now[topsort[i]] = 1;
  87.                               }
  88.  
  89.                               for(list<int>::iterator K = graf[topsort[i]].begin(); K != graf[topsort[i]].end(); K++){
  90.                                       where_now[*K] = max(where_now[*K], where_now[topsort[i]] + 1);
  91.                                       maks = max(maks, where_now[*K]);
  92.                               }
  93.                       }
  94.  
  95.                       vector <int> tab[maks + 1];
  96.  
  97.                       for(int i = topsort.size() - 1; i >= 0; i--){
  98.                               tab[where_now[topsort[i]]].push_back(topsort[i]);
  99.                       }
  100.  
  101.                       cout << "TAK " << maks << endl;
  102.                       for(int i = 1; i <= maks; i++){
  103.                               cout << tab[i].size() << " ";
  104.                               for(int j = 0; j < (int)tab[i].size(); j++){
  105.                                       cout << tab[i][j] << " ";
  106.                               }
  107.  
  108.                               cout << endl;
  109.                       }
  110.               }
  111.               for(int i = 1; i <= V; i++){
  112.                       graf[i].clear();
  113.               }
  114.  
  115.               delete [] graf;
  116.               delete [] color;
  117.               delete [] where_now;
  118.       }
  119.       return 0;
  120. }