2021-2022 ICPC, NERC, Northern Eurasia Onsite Problem-L. Labyrinth

本文主要是介绍2021-2022 ICPC, NERC, Northern Eurasia Onsite Problem-L. Labyrinth，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

可能是今年我写的最漂亮的一题（毕竟蒟蒻A大题

传送门：Problem - L - Codeforces (Unofficial mirror site, accelerated for Chinese users)

题意：有向图，两个人从出发点开始从两条不同的路走到终点，出发点给定，终点任选（除出发点外）。

注意：可能成环！可能非连通图！（写着写着把成环忘了，RE两发血亏TAT）

/*样例
输入
5 5 1
1 2
2 3
1 4
4 3
3 5
输出
Possible
3
1 2 3
3
1 4 3输入
5 5 1
1 2
2 3
3 4
2 5
5 4
输出
Impossible输入
3 3 2
1 2
2 3
3 1
输出
Impossible*/

我的做法是记忆化深搜（自己取名装高手

思路很简单，从指定出发点开始，对出发点能一步到达的所有顶点深搜，要是其中存在两次深搜在某个点碰头了，就说明有路径（Possible），否则没有。

~~嗯很清晰的思路，但是有点难写呢~~~

考虑这样使用vis数组，每次深搜把路径上每个点u的vis[u]赋予出发点si（好像没说清，就是vis[u]=si），那深搜的细节操作就很明晰了

当vis[u]为0时，说明没探索过这个点，给vis[u]赋si，return 0
当vis[u]为本次深搜的出发点时（vis[u] && vis[u] == si），说明发现环了，return 0
当vis[u]不为0，且不等于本次深搜的出发点时（vis[u] && vis[u] != si），说明发现与之前某次深搜碰头了，咱们先输出这次深搜记录的路径（ans），然后返回碰头的节点，以便通过vis找与本次深搜碰头的那次深搜的出发点

#include<bits/stdc++.h>
using namespace std;
const int maxe = 2e5+100;
int cnt;
struct node{int to, next;
}edge[maxe];int head[maxe], vis[maxe];vector<int> ans;void add(int u,int v){edge[++cnt].to = v;edge[cnt].next = head[u];head[u] = cnt;
}
int an, s;
int dfs(int u, int v, int si){if(u == s) return 0;if(vis[u] && vis[u] != si){if(an == 0){printf("Possible\n");an++;}printf("%d\n", ans.size() + 2);for(int i = 0; i < ans.size(); i++){printf("%d ", ans[i]);}printf("%d %d\n", v, u);return u;}if(vis[u]&&vis[u]==si) return 0;vis[u] = si;int f = 0;for(int i = head[u]; i; i = edge[i].next) {ans.push_back(v);f = dfs(edge[i].to, u, si);ans.pop_back();if(f) return f;}return 0;
}
int main(){int n,m;scanf("%d%d%d", &n, &m, &s);for(int i = 1; i <= m; i++){int a,b;scanf("%d%d", &a, &b);add(a, b);}int f=0, ff=0;for(int i=head[s];i;i=edge[i].next){f = dfs(edge[i].to, s, edge[i].to);if(f){ff = edge[i].to;break;}}if(f){int tmp = vis[f];for(int i=1;i<=n;i++) vis[i] = 0;vis[f] = ff;f = tmp;dfs(f, s, f);}else{printf("Impossible");}return 0;
}

最后夸夸队友一发没WA，希望EC也能做个两题\doge