题目分析:

  首先观察可知这是一个无向图,那么我们构建出它的dfs树。由于无向图的性质我们可以知道它的dfs树只有返祖边。考虑下面这样一个结论。

  首先我们证明S和T肯定在DFS树中是祖先关系,接着证明到T至少有一条返祖边,那么这个结论就是显然的了。

代码:

 #include<bits/stdc++.h>
using namespace std; const int maxn = ; int n,m;
vector <int>g[maxn]; int up[maxn],dep[maxn],wh[maxn],fa[maxn];
int flag, from, to; void read(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) g[i].clear();
for(int i=;i<=m;i++){
int u,v; scanf("%d%d",&u,&v);
g[u].push_back(v); g[v].push_back(u);
}
} int r1[maxn],num1;
int r2[maxn],num2;
int r3[maxn],num3;
int md;
stack <int> s;
void print(int now){
int pla = now;
while(dep[pla] != to) r1[++num1] = pla,pla = fa[pla];
r1[++num1] = pla; pla = md;
while(dep[pla] != dep[now]) s.push(pla),pla = fa[pla];
s.push(pla);
while(!s.empty()){r2[++num2] = s.top();s.pop();}
r2[++num2] = r1[num1]; pla = wh[now];
while(dep[pla] != dep[now]) s.push(pla),pla = fa[pla];
s.push(pla);
while(!s.empty()){r3[++num3] = s.top();s.pop();}
pla = r1[num1];
while(dep[pla] != up[now]) s.push(pla),pla = fa[pla];
s.push(pla);
while(!s.empty()){r3[++num3] = s.top();s.pop();} printf("%d %d\n",r1[],r1[num1]);
printf("%d ",num1);for(int i=;i<=num1;i++) printf("%d ",r1[i]);
puts("");
printf("%d ",num2);for(int i=;i<=num2;i++) printf("%d ",r2[i]);
puts("");
printf("%d ",num3);for(int i=;i<=num3;i++) printf("%d ",r3[i]);
puts("");flag = ;
} void dfs(int now,int dp){
dep[now] = dp;
for(int i=;i<g[now].size();i++){
int nxt = g[now][i];
if(fa[now] == nxt) continue;
if(flag) break;
if(dep[nxt] == ){
fa[nxt] = now;
dfs(nxt,dp+); if(flag) break;
if(up[nxt] >= dep[now]) continue;
if(up[now] >= ) up[now] = up[nxt],wh[now] = wh[nxt];
else{
if(up[now] <= up[nxt]){
from = now; to = up[nxt];md = wh[nxt];
}else {
from = now; to = up[now];up[now] = up[nxt];
md = wh[now];wh[now]= wh[nxt];
}
print(from);
}
}else{
if(dep[nxt] > dep[now]) continue;
if(up[now] >= ) up[now] = dep[nxt],wh[now] = now;
else{
if(up[now] <= dep[nxt]){
from = now; to = dep[nxt];md = now;
}else {
from = now; to = up[now];up[now] = dep[nxt];
md = wh[now];wh[now] = now;
}
print(from);
}
}
}
} void work(){
flag = ; from = ; to = ; num1 = num2 = num3 = ;
for(int i=;i<=n;i++) wh[i] = ,fa[i] = ,dep[i] = ,up[i] = 1e9;
for(int i=;i<=n;i++) if(!dep[i]) dfs(i,);
if(!flag){puts("-1");}
} int main(){
int cas; scanf("%d",&cas);
while(cas--){
read();
work();
}
return ;
}
05-11 14:07