Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <cstring>
- #include <algorithm>
- #include <bitset>
- #include <stack>
- #include <queue>
- #define task ""
- using namespace std;
- using ll = long long;
- using ld = long double;
- const int N = 15e4 + 2;
- const int Inf = 1e9 + 7;
- int n, m, l(0), low[N], num[N], cnt(0);
- int par[N], x[N], deg[N], pos[N], in[N], out[N];
- bool ok[N];
- vector<int> adj[N],
- direct[N],
- lt[N],
- st,
- nadj[N];
- int findpar(int v)
- {
- return par[v] < 0 ? v : par[v] = findpar(par[v]);
- }
- void Read()
- {
- cin >> n >> m;
- memset(par, -1, sizeof par);
- for (int i = 1; i <= m; ++i)
- {
- int u, v;
- cin >> u >> v;
- int x = findpar(u),
- y = findpar(v);
- if (x != y)
- {
- par[x] += par[y];
- par[y] = x;
- }
- direct[u].push_back(v);
- }
- }
- void dfs(int v)
- {
- num[v] = low[v] = ++cnt;
- st.push_back(v);
- for (auto i : direct[v])
- if (num[i])
- low[v] = min(low[v], num[i]);
- else
- {
- dfs(i);
- low[v] = min(low[v], low[i]);
- }
- if (low[v] == num[v])
- {
- ++l;
- int t;
- do
- {
- t = st.back();
- lt[l].push_back(t);
- st.pop_back();
- low[t] = num[t] = Inf;
- par[t] = l;
- } while (v != t);
- }
- }
- void tarjan()
- {
- for (int i = 1; i <= n; ++i)
- if (!num[i])
- dfs(i);
- }
- void topoSort()
- {
- stack<int> q;
- for (int i = 1; i <= l; ++i)
- {
- deg[i] = nadj[i].size();
- if (deg[i] == 0)
- q.push(i);
- }
- int piv = 0;
- while (q.size())
- {
- x[++piv] = q.top();
- pos[x[piv]] = piv;
- q.pop();
- for (auto i : adj[x[piv]])
- {
- --deg[i];
- if (deg[i] == 0)
- q.push(i);
- }
- }
- }
- void Solve()
- {
- vector<bool> ck(N);
- int check = 0;
- for (int i = 1; i <= n; ++i)
- {
- int v = findpar(i);
- if (!ck[v])
- {
- ++check;
- ck[v] = 1;
- }
- }
- if (check > 1)
- {
- cout << 0;
- return;
- }
- tarjan();
- for (int i = 1; i <= n; ++i)
- {
- for (auto j : direct[i])
- {
- if (par[i] != par[j])
- {
- adj[par[i]].push_back(par[j]);
- nadj[par[j]].push_back(par[i]);
- }
- }
- }
- for (int i = 1; i <= l; ++i)
- {
- sort(adj[i].begin(), adj[i].end());
- adj[i].resize(unique(adj[i].begin(), adj[i].end()) - adj[i].begin());
- sort(nadj[i].begin(), nadj[i].end());
- nadj[i].resize(unique(nadj[i].begin(), nadj[i].end()) - nadj[i].begin());
- in[i] = nadj[i].size();
- out[i] = adj[i].size();
- }
- topoSort();
- vector<int> a;
- int Lef(0), Rig(0);
- for (int i = 1; i <= l; ++i)
- if (in[x[i]] == 0)
- ++Rig;
- for (int i = 1; i <= l; ++i)
- {
- if (in[x[i]] == 0)
- --Rig;
- for (auto j : nadj[x[i]])
- {
- if (out[j] == 0)
- --Lef;
- ++out[j];
- }
- if (Lef == 0 && Rig == 0)
- {
- for (auto j : lt[x[i]])
- a.push_back(j);
- }
- for (auto j : adj[x[i]])
- {
- --in[j];
- --out[x[i]];
- if (in[j] == 0)
- ++Rig;
- }
- if (out[x[i]] == 0)
- ++Lef;
- }
- sort(a.begin(), a.end());
- cout << a.size() << "\n";
- for (auto i : a)
- cout << i << " ";
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if (fopen(task ".INP", "r"))
- freopen(task ".INP", "r", stdin),
- freopen(task ".OUT", "w", stdout);
- Read();
- Solve();
- }
- /*
- 5 5
- 1 2
- 2 3
- 3 5
- 4 5
- 2 4
- */
Advertisement
Add Comment
Please, Sign In to add comment