SHARE
TWEET

Untitled

a guest Sep 15th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <stack>
  5. using namespace std;
  6.  
  7. int n;
  8. int m;
  9.  
  10. bool odw[1000000+5];
  11.  
  12. int SSS[1000000+5];
  13. int krawedzie[1000000+5][2];
  14. int sorted_SSS[1000000+5];
  15. int co_na_pozycji_sorted[1000000+5];
  16. int max_SSS_na_sciezce[1000000+5];
  17. int ile_opcji_dojscia[1000000+5];
  18.  
  19.  
  20. bool czy_jest_petla[1000000+5];
  21. vector <int> sas[1000000+5];
  22. vector <int> sas_rev[1000000+5];
  23. vector <int> sas_SSS_rev[1000000+5];
  24. vector <int> zawartosc_SSS[1000000+5];
  25. stack <int> S;
  26.  
  27. void DFS_make_stack(int i)
  28. {
  29.     odw[i] = 1;
  30.  
  31.     for(int j=0; j<sas[i].size(); j++)
  32.         if(!odw[sas[i][j]])
  33.             DFS_make_stack(sas[i][j]);
  34.  
  35.     S.push(i);
  36. }
  37.  
  38. void DFS_make_SSS(int w, int nr_SSS)
  39. {
  40.     odw[w] = 1;
  41.     //cout<<"w: "<<w<<" nr_SSS: "<<nr_SSS<<endl;
  42.     SSS[w] = nr_SSS;
  43.     zawartosc_SSS[nr_SSS].push_back(w);
  44.  
  45.     for(int i=0; i<sas_rev[w].size(); i++)
  46.         if(!odw[sas_rev[w][i]])
  47.             DFS_make_SSS(sas_rev[w][i], nr_SSS);
  48. }
  49. int nr = 1;
  50.  
  51. void DFS_topo(int w)
  52. {
  53.     odw[w] = 1;
  54.  
  55.     for(int i=0; i<sas_SSS_rev[w].size(); i++)
  56.         if(!odw[sas_SSS_rev[w][i]])
  57.             DFS_topo(sas_SSS_rev[w][i]);
  58.     sorted_SSS[w] = nr;
  59.     co_na_pozycji_sorted[nr] = w;
  60.     nr++;
  61. }
  62.  
  63.  
  64. int main()
  65. {
  66.     cin>>n;
  67.     cin>>m;
  68.  
  69.     int t1;
  70.     int t2;
  71.  
  72.     for(int i=1; i<=m; i++)
  73.     {
  74.         cin>>t1;
  75.         cin>>t2;
  76.  
  77.         krawedzie[i][0] = t1;
  78.         krawedzie[i][1] = t2;
  79.  
  80.         if(t1==t2)
  81.             czy_jest_petla[t1] = 1;
  82.  
  83.         sas[t1].push_back(t2);
  84.         sas_rev[t2].push_back(t1);
  85.     }
  86.  
  87.     for(int i=1; i<=(n+1); i++)
  88.         if(!odw[i])
  89.             DFS_make_stack(i);
  90.  
  91.  
  92.     for(int i=1; i<=(n+1); i++)
  93.         odw[i] = 0;
  94.     ///ODWRACAM KRAWEDZIE -> KORZYSTAM Z SAS_REV
  95.  
  96.     int top;
  97.  
  98.     while(!S.empty())
  99.     {
  100.         top = S.top();
  101.         //cout<<"top: "<<top<<endl;
  102.         if(!odw[top])
  103.             DFS_make_SSS(top, top);
  104.  
  105.         S.pop();
  106.     }
  107.  
  108.     for(int i=1; i<=(n+1); i++)
  109.         odw[i] = 0;
  110.    // for(int i=1; i<=(n+1); i++)
  111.      //   cout<<"i: "<<i<<" SSS: "<<SSS[i]<<" roz: "<<roz_SSS[i]<<endl;
  112.      for(int i=1; i<=m; i++)
  113.      {
  114.         int od_ = SSS[krawedzie[i][0]];
  115.         int do_ = SSS[krawedzie[i][1]];
  116.  
  117.         if(od_ != do_)
  118.         {
  119.             sas_SSS_rev[do_].push_back(od_);
  120.         }
  121.      }
  122.  
  123.      DFS_topo(n+1);
  124.     vector<int> zawsze;
  125.  
  126.         //cout<<"sas_SSS_rev[4][0]: "<<sas_SSS_rev[4][0]<<endl;
  127.  
  128.    // for(int i=1; i<=4; i++)
  129.      //   cout<<"i: "<<i<<" co: "<<co_na_pozycji_sorted[i]<<endl;
  130.  
  131.  
  132.      for(int i=sorted_SSS[n+1]; i>=1; i--)
  133.      {
  134.             int SSS_ = co_na_pozycji_sorted[i];
  135.            // cout<<"SSS_: "<<SSS_<<endl;
  136.             if(SSS_ == (n+1) || max_SSS_na_sciezce[SSS_] != 0)
  137.             {
  138.                 max_SSS_na_sciezce[SSS_] = max(max_SSS_na_sciezce[SSS_], int(zawartosc_SSS[SSS_].size()));
  139.                 if(czy_jest_petla[SSS_])
  140.                     max_SSS_na_sciezce[SSS_]++;
  141.  
  142.                 if(max_SSS_na_sciezce[SSS_] > 1)
  143.                     zawsze.push_back(SSS_);
  144.  
  145.                 for(int j=0; j<sas_SSS_rev[SSS_].size(); j++)
  146.                     {//cout<<"sas: "<<sas_SSS_rev[SSS_][j]<<endl;
  147.                     max_SSS_na_sciezce[sas_SSS_rev[SSS_][j]] = max(max_SSS_na_sciezce[sas_SSS_rev[SSS_][j]], max_SSS_na_sciezce[SSS_]);}
  148.             }
  149.      }
  150.  
  151.    //  cout<<zawsze.size()<<endl;
  152.    //  for(int i=0; i<zawsze.size(); i++)
  153.      //   cout<<zawsze[i]<<endl;
  154.  
  155.  
  156.         ile_opcji_dojscia[n+1] = 1; ///
  157.         for(int i=sorted_SSS[n+1]; i>=1; i--)
  158.      {
  159.             int SSS_ = co_na_pozycji_sorted[i];
  160.           //  cout<<"SSS_: "<<SSS_<<endl;
  161.  
  162.                 for(int j=0; j<sas_SSS_rev[SSS_].size(); j++)
  163.                     {//cout<<"sas: "<<sas_SSS_rev[SSS_][j]<<endl;
  164.                     ile_opcji_dojscia[sas_SSS_rev[SSS_][j]] += ile_opcji_dojscia[SSS_];}
  165.             if(ile_opcji_dojscia[SSS_] > 36500)
  166.                 zawsze.push_back(SSS_);
  167.  
  168.      }
  169.  
  170.      vector<int>zawsze_w;
  171.  
  172.      for(int i=0; i<zawsze.size(); i++)
  173.      {
  174.         int SSS_ = zawsze[i];
  175.         for(int j=0; j<zawartosc_SSS[SSS_].size(); j++)
  176.         {
  177.             zawsze_w.push_back(zawartosc_SSS[SSS_][j]);
  178.         }
  179.      }
  180.  
  181.      if(zawsze_w.size() > 0)
  182.      {
  183.         cout<<"zawsze"<<endl;
  184.         cout<<zawsze_w.size()<<endl;
  185.         sort(zawsze_w.begin(), zawsze_w.end());
  186.         for(int i=0; i<zawsze_w.size(); i++)
  187.             cout<<zawsze_w[i]<<' ';
  188.  
  189.      }
  190.      else
  191.      {
  192.         int max_ = 0;
  193.         for(int i=1; i<=n; i++)
  194.             max_ = max(max_, ile_opcji_dojscia[i]);
  195.  
  196.         int ile = 0;
  197.         for(int i=1; i<=n; i++)
  198.            if(ile_opcji_dojscia[i] == max_)
  199.             ile++;
  200.         cout<<max_<<endl;
  201.         cout<<ile<<endl;
  202.  
  203.         for(int i=1; i<=n; i++)
  204.            if(ile_opcji_dojscia[i] == max_)
  205.             cout<<i<<' ';
  206.  
  207.      }
  208.  
  209.     return 0;
  210. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top