Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <cmath>
- #include <queue>
- using namespace std;
- #define forn(i, n) for(size_t i = 0; i < (n); i++)
- #define mp make_pair
- typedef pair<int, bool> pib;
- typedef pair<int, int> pii;
- const int inf = 1000000000;
- vector<vector<int> > g;
- vector<vector<int> > gtr;
- vector<vector<int> > paths;
- vector<int> dots;
- int n, m;
- void front_find(int u, vector<int> &d, vector<bool> &used, queue<pib> &q, bool stop) {
- if (stop) return;
- for (size_t i = 0; i < g[u].size(); ++i) {
- int to = g[u][i];
- if (d[to] == inf) {
- d[to] = d[u] + 1;
- paths[to].push_back(u);
- used[to] = true;
- q.push(mp(to, true));
- }
- else if (d[u] + 1 == d[to])
- paths[to].push_back(u);
- }
- }
- void back_find(int u, vector<int> &d, vector<bool> &used, queue<pib> &q, bool &stop) {
- for (size_t i = 0; i < gtr[u].size(); ++i) {
- int to = gtr[u][i];
- if (used[to]) {
- paths[u].push_back(to); // Сомнительный момент, ответ из-за этого дублируется иногда
- dots.push_back(to + 1);
- stop = true;
- continue;
- }
- if (d[to] == inf && !stop) {
- d[to] = d[u] + 1;
- paths[u].push_back(to);
- q.push(mp(to, false));
- }
- }
- }
- void find_path(int s, int f) {
- queue<pib> q;
- vector<int> d(n, inf);
- vector<int> dtr(n, inf);
- paths.resize(n, vector<int>());
- bool stop = false;
- vector<bool> used(n);
- used[s] = true;
- used[f] = true;
- d[s] = 0;
- dtr[f] = 0;
- q.push(mp(s, true));
- q.push(mp(f, false));
- while (!q.empty()) {
- pib u = q.front();
- q.pop();
- if (u.second)
- front_find(u.first, d, used, q, stop);
- else
- back_find(u.first, dtr, used, q, stop);
- }
- }
- int dp = 0;
- void create_paths(int u, vector<vector<int> > &result, vector<int> &arr, int deep) {
- arr.push_back(u + 1);
- for (size_t i = 0; i < paths[u].size(); i++) {
- int to = paths[u][i];
- create_paths(to, result, arr, deep + 1);
- }
- dp = max(dp, deep);
- if (dp == deep)
- result.push_back(arr);
- arr.pop_back();
- }
- void vec_print(vector<int>::iterator begin, vector<int>::iterator end) {
- for (auto it = begin; it != end; it++)
- cout << *it << " ";
- cout << endl;
- }
- int main() {
- //#ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- //#endif
- ios_base::sync_with_stdio(false);
- cin >> n >> m;
- int v1, v2;
- cin >> v1 >> v2;
- v1--, v2--;
- g.resize(n, vector<int>());
- gtr.resize(n, vector<int>());
- for (int i = 0; i < m; i++) {
- int x, y;
- cin >> x >> y;
- x--, y--;
- g[x].push_back(y);
- gtr[y].push_back(x);
- }
- find_path(v1, v2);
- vec_print(dots.begin(), dots.end());
- vector<vector<int> > result;
- vector<int> temp;
- int deep = 0;
- create_paths(v2, result, temp, deep);
- for (size_t i = 0; i < result.size(); i++)
- vec_print(result[i].begin(), result[i].end());
- return 0;
- }
- /*
- input.txt
- 9 16
- 1 9
- 1 2
- 1 4
- 2 3
- 2 5
- 2 6
- 3 1
- 3 8
- 4 3
- 5 6
- 5 7
- 6 7
- 6 8
- 7 8
- 8 4
- 8 9
- 9 6
- */
- /*
- output.txt
- 3 6
- 9 8 3 2 1
- 9 8 3 4 1
- 9 8 6 2 1
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement