Gym101612 Problem G. Grand Test（tarjan，low值应用）

本文主要是介绍Gym101612 Problem G. Grand Test（tarjan，low值应用），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
问图中是否存在两个点使得两个点存在至少三条不交叉路径，输出这三条路径。

思路：
被PC拉过来写，写了一个晚上还是不会XXX。
最后参考了题解的写法：记录下每个点的次大low值和最大low值以及对应的点，由此回溯路径就可以保证不交叉了。

本题实际就是找两个环拼在一起的情况。

首先一开始的写法是在点双连通分量里面找到一个度数大于等于3的点，再从这个点出发找到另外一个度数大于等于3的点。因为点双连通分量里面的点一定在环上（排除孤立点），如果度数大于等于3那就说明在不止一个环上，那就一定存在至少三条路径。

再跑dfs找出这两个点所连的三条路径。但是这有个问题，这三条路径确实存在，但是你dfs的过程可能会使得其交叉。用过各种方法（bfs，3条路径同时跑，找最短的先跑等等）。

题解的方法很巧妙，就是维护每个点能到达的最小dfs序low1和次小dfs序low2。
只要存在low2[x]<dfn[x]，就说明这个点存在次小能到达dfs序，在跑tarjan的过程中顺带维护每个点上一个节点，再跑回溯就能找到三条不相交路径了。

node存的是对应时序的点，end1[x]代表最小能到达dfs序的点，end2[x]为次小能到达dfs序的点。
起点为x，终点为node[low2[x]]
具体为：

从 $x$ 到 $n o d e [l o w 2 [x]]$ 。
从 $x$ 到 $n o d e [l o w 1 [x]]$ ，再从 $n o d e [l o w 1 [x]] 到 n o d e [l o w 2 [x]]$ 。
从 $x$ 到 $e n d 2 [x]$ ，再从 $e n d 2 [x]$ 到 $n o d e [l o w 2 [x]]$ 。

总之，这道题加深了我对low值的理解。
只要一个点存在能到达的最小dfs序值（比当前小），那么就说明该点出发能到达之前到过的点，也就是成环。
如果存在次小low值，那就说明存在两条边能到达之前到过的点，那就成了两个环相交。

我们可以再拓展，如果题目要求两点有4条不相交路径，那实际就是3个环拼在一起的情况，再维护次次小low值就好了。
也可以类似的找出这四条路径。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>using namespace std;const int maxn = 1e5 + 7;int dfn[maxn],low1[maxn],low2[maxn],end1[maxn],end2[maxn],node[maxn],cnt;
int head[maxn],nex[maxn * 2],to[maxn * 2],tot;
int Fa[maxn];void add(int x,int y) {to[++tot] = y;nex[tot] = head[x];head[x] = tot;
}void update(int x,int d,int y) {if(d < low1[x]) {low2[x] = low1[x];end2[x] = end1[x];low1[x] = d;end1[x] = y;} else if(d < low2[x]) {low2[x] = d;end2[x] = y;}
}vector<int>get_path(int s,int t,bool flag) { //flag代表是否需要反转vector<int>path;for(int i = s;i != t;i = Fa[i]) {path.push_back(i);}path.push_back(t);if(flag) reverse(path.begin(),path.end());return path;
}void print_path(vector<int>path) {printf("%d ",path.size());for(int i = 0;i < path.size();i++) {printf("%d ",path[i]);}printf("\n");
}int flag = 0;
void tarjan(int x,int fa) {if(flag) return;dfn[x] = low1[x] = low2[x] = ++cnt;node[cnt] = end1[x] = end2[x] = x;for(int i = head[x];i;i = nex[i]) {int v = to[i];if(v == fa) continue;if(!dfn[v]) {Fa[v] = x;tarjan(v,x);update(x,low1[v],end1[v]);} else if(dfn[v] < dfn[x]) {update(x,dfn[v],x);}}if(!flag && low2[x] < dfn[x]) {int s = x,t = node[low2[x]];printf("%d %d\n",s,t);vector<int>path;path = get_path(s,t,false);print_path(path);path = get_path(end2[x],s,true);path.push_back(t);print_path(path);vector<int>path1,path2;path1 = get_path(end1[x],s,true);path2 = get_path(t,node[low1[x]],true);path1.insert(path1.end(),path2.begin(),path2.end());print_path(path1);flag = 1;}
}void init(int n) {tot = 1;cnt = 0;flag = 0;for(int i = 1;i <= n;i++) {low1[i] = low2[i] = end1[i] = end2[i] = node[i] = 0;Fa[i] = dfn[i] = head[i] = 0;}
}int main() {freopen("grand.in","r",stdin);freopen("grand.out","w",stdout);int T;scanf("%d",&T);while(T--) {int n,m;scanf("%d%d",&n,&m);init(n);for(int i = 1;i <= m;i++) {int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}for(int i = 1;i <= n;i++) {if(!dfn[i]) tarjan(i,-1);}if(!flag) {printf("-1\n");}}return 0;
}