Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAXN 1000006
- #define EVER 36501
- using namespace std;
- int n,m,a,b;
- vector <bool> Pross(MAXN, false);
- vector <int> Ans(MAXN, 0);
- void DFS (int v, vector <vector <int> > &G, vector <bool> &V, vector <bool> &C)
- {
- V[v] = true;
- Pross[v] = true;
- for (auto nei:G[v])
- {
- if (V[nei] == false) DFS(nei, G, V, C);
- else if (Pross[nei]) C[v] = true;
- }
- Pross[v] = false;
- }
- void DFS2 (int v, vector <vector <int> > &G, vector <bool> &V)
- {
- V[v] = true;
- Ans[v] = EVER;
- for (auto nei:G[v])
- {
- if (V[nei] == false) DFS2(nei, G, V);
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin >> n >> m;
- n++;
- vector <vector <int> > Trans(n);
- vector <bool> vis(n, false);
- vector <bool> onCycle(n, false);
- vector <int> DegIn(n, 0);
- while (m--)
- {
- cin >> a >> b;
- a--, --b;
- Trans[b].push_back(a);
- DegIn[a]++;
- }
- DFS(n-1, Trans, vis, onCycle);
- for (int i=0; i!=n; ++i) if (vis[i] == false) Ans[i] = -1;
- for (int i=0; i!=n; ++i) vis[i] = false;
- for (int i=0; i!=n; ++i) if (onCycle[i] && vis[i] == false) DFS2(i, Trans, vis);
- for (int i=0; i!=n; ++i) vis[i] = false;
- for (int i=0; i!=n; ++i) if (Ans[i] != 0)
- {
- for (auto nei:Trans[i]) DegIn[nei]--;
- vis[i] = true;
- }
- queue <int> Q;
- for (int i=0; i!=n; ++i) if (DegIn[i] == 0 && Ans[i] == 0) Q.push(i);
- Ans[n-1] = 1;
- while (Q.empty() == false)
- {
- int node = Q.front();
- Q.pop();
- for (auto nei:Trans[node])
- {
- Ans[nei] = min(EVER, Ans[nei] + Ans[node]);
- DegIn[nei]--;
- if (DegIn[nei] == 0) Q.push(nei);
- }
- }
- int maxVal = -1;
- for (auto v:Ans) maxVal = max(maxVal, v);
- for (int i=0; i!=n; ++i) if (Ans[i] == maxVal) Q.push(i+1);
- if (maxVal == EVER) cout << "zawsze";
- else cout << maxVal;
- cout << "\n" << Q.size() << "\n";
- while (Q.empty() == false)
- {
- cout << Q.front() << " ";
- Q.pop();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement