Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstdio>
- #include <string>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- vector<vector<int> > g;
- vector<int> order, used, check;
- vector<pair<int, int> > edge;
- void dfs(int v)
- {
- used[v] = 1;
- for (int i = 0; i < g[v].size(); i++)
- {
- int to = g[v][i];
- if (!used[to])
- dfs(to);
- }
- order.push_back(v);
- }
- int main()
- {
- int n, m;
- cin >> n >> m;
- g.resize(n);
- check.assign(n, 0);
- int x, y;
- for (int i = 0; i < n; i++)
- {
- cin >> x >> y;
- x--;
- y--;
- g[x].push_back(y);
- }
- used.assign(n, 0);
- for (int i = 0; i < n; i++)
- {
- if (!used[i])
- dfs(i);
- }
- check[0] = -1;
- for (int i = order.size() - 1; i >= 0; i--)
- {
- int v = order[i];
- for (int j = 0; j < g[v].size(); j++)
- {
- int to = g[v][j];
- edge.push_back({ v, to });
- }
- }
- for (int i = 0; i < edge.size(); i++)
- {
- int to = edge[i].second;
- int from = edge[i].first;
- if (check[from] == 0)
- continue;
- if (check[to] == 0)
- {
- if (check[from] == -1)
- check[to] = i+1;
- else
- {
- check[to] = check[from];
- }
- }
- else
- if (check[from] != -1)
- {
- check[to] = -1;
- }
- else
- {
- if (check[from] != check[to])
- check[to] = -1;
- else
- check[to] = min(check[to], check[from]);
- }
- }
- int ans = 0;
- for (int i = 0; i < n; i++)
- if (check[i] <= 0)
- ans++;
- cout << ans << endl;
- for (int i = 0; i < n; i++)
- if (check[i] <= 0)
- cout << i + 1 << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement