Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- vector<int> in[100000], out[100000];
- int used[100000];
- vector<int> done;
- int prev1[100000];
- vector<int> ans, res;
- int a, b;
- int dfs(int u)
- {
- if (used[u] == 1)
- return 0;
- if (u == b)
- {
- int v = b;
- while (v != -1)
- {
- res.push_back(v);
- v = prev1[v];
- }
- reverse(res.begin(), res.end());
- return 1;
- }
- used[u] = 1;
- for (int j = 0; j < out[u].size(); j++)
- {
- int v = out[u][j];
- if (!used[v])
- {
- prev1[v] = u;
- if (dfs(v))
- return 1;
- }
- }
- return 0;
- }
- int main()
- {
- cout.sync_with_stdio(0);
- int n, m, p, q;
- cin >> n >> m >> a >> b;
- a--, b--;
- for (int i = 0; i < n; i++)
- used[i] = 0;
- for (int i = 0; i < m; i++)
- {
- cin >> p >> q;
- out[p - 1].push_back(q - 1);
- in[q - 1].push_back(p - 1);
- }
- prev1[a] = -1;
- dfs(a);
- int cnt = 0;
- int k = (int)res.size();
- int up[k], down[k];
- for (int i = 0; i < k; i++)
- {
- up[i] = 0;
- if (!i)
- down[i] = 0;
- else
- down[i] = 1;
- }
- for (int i = 0; i < (int)res.size(); i++)
- {
- if (i > 0)
- up[i - 1] = -1;
- down[i] = 0;
- for (int j = 0; j < in[i].size(); j++)
- {
- int v = in[i][j];
- cnt += up[v];
- }
- //cout << res[i] + 1 << " " << cnt << endl;
- if (cnt == 0 && res[i] != a && res[i] != b)
- ans.push_back(res[i] + 1);
- for (int j = 0; j < out[i].size(); j++)
- {
- int v = out[i][j];
- cnt += down[v];
- }
- }
- cout << ans.size() << endl;
- sort(ans.begin(), ans.end());
- for (int i = 0; i < (int)ans.size(); i++)
- cout << ans[i] << " ";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement