BZOJ5203 [NEERC2017 Northern] Grand Test 【dfs树】【构造】

题目分析：

　　首先观察可知这是一个无向图，那么我们构建出它的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 ;

 }