Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Dec 6th, 2018 69 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. #include <bits/stdc++.h>
  2. #define MAXN 1000006
  3. #define EVER 36501
  4. using namespace std;
  5. int n,m,a,b;
  6. vector <bool> Pross(MAXN, false);
  7. vector <int> Ans(MAXN, 0);
  8. void DFS (int v, vector <vector <int> > &G, vector <bool> &V, vector <bool> &C)
  9. {
  10.     V[v] = true;
  11.     Pross[v] = true;
  12.     for (auto nei:G[v])
  13.     {
  14.         if (V[nei] == false) DFS(nei, G, V, C);
  15.         else if (Pross[nei]) C[v] = true;
  16.     }
  17.     Pross[v] = false;
  18. }
  19.  
  20. void DFS2 (int v, vector <vector <int> > &G, vector <bool> &V)
  21. {
  22.     V[v] = true;
  23.     Ans[v] = EVER;
  24.     for (auto nei:G[v])
  25.     {
  26.         if (V[nei] == false) DFS2(nei, G, V);
  27.     }
  28. }
  29.  
  30. int main()
  31. {
  32.     ios_base::sync_with_stdio(0);
  33.     cin.tie(0);
  34.     cout.tie(0);
  35.  
  36.     cin >> n >> m;
  37.     n++;
  38.     vector <vector <int> > Trans(n);
  39.     vector <bool> vis(n, false);
  40.     vector <bool> onCycle(n, false);
  41.     vector <int> DegIn(n, 0);
  42.  
  43.     while (m--)
  44.     {
  45.         cin >> a >> b;
  46.         a--, --b;
  47.         Trans[b].push_back(a);
  48.         DegIn[a]++;
  49.     }
  50.     DFS(n-1, Trans, vis, onCycle);
  51.     for (int i=0; i!=n; ++i) if (vis[i] == false) Ans[i] = -1;
  52.     for (int i=0; i!=n; ++i) vis[i] = false;
  53.  
  54.     for (int i=0; i!=n; ++i) if (onCycle[i] && vis[i] == false) DFS2(i, Trans, vis);
  55.     for (int i=0; i!=n; ++i) vis[i] = false;
  56.     for (int i=0; i!=n; ++i) if (Ans[i] != 0)
  57.         {
  58.             for (auto nei:Trans[i]) DegIn[nei]--;
  59.             vis[i] = true;
  60.         }
  61.  
  62.     queue <int> Q;
  63.     for (int i=0; i!=n; ++i) if (DegIn[i] == 0 && Ans[i] == 0) Q.push(i);
  64.     Ans[n-1] = 1;
  65.  
  66.     while (Q.empty() == false)
  67.     {
  68.         int node = Q.front();
  69.         Q.pop();
  70.  
  71.         for (auto nei:Trans[node])
  72.         {
  73.             Ans[nei] = min(EVER, Ans[nei] + Ans[node]);
  74.             DegIn[nei]--;
  75.             if (DegIn[nei] == 0) Q.push(nei);
  76.         }
  77.     }
  78.  
  79.     int maxVal = -1;
  80.     for (auto v:Ans) maxVal = max(maxVal, v);
  81.     for (int i=0; i!=n; ++i) if (Ans[i] == maxVal) Q.push(i+1);
  82.     if (maxVal == EVER) cout << "zawsze";
  83.     else cout << maxVal;
  84.     cout << "\n" << Q.size() << "\n";
  85.     while (Q.empty() == false)
  86.     {
  87.         cout << Q.front() << " ";
  88.         Q.pop();
  89.     }
  90.     return 0;
  91. }
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