题解：AT_abc251_f Two Spanning Trees

· · 题解

本文同步于我的ABC251~300 板刷记录。

考虑没有前向边的搜索树。

全部非树边均为祖先关系，即为返祖边，无横叉边，使用任意一棵 dfs 树即可。

均非祖先关系，即为横叉边，无返祖边，即可使用图的 bfs 树。

注意两棵树不一定不同。

#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    } 
    return a*b;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
const int N=5*114514; 
int n,m;
vector<int> g[N];
int fa1[N],fa2[N];  //分别代表 dfs 的父亲和 bfs 的父亲 
void dfs(int u){
//  cout<<'!'<<u<<endl;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
//      cout<<'#'<<v<<endl;
        if(!fa1[v]){
            fa1[v]=u;
            write1(u),write2(v);
            dfs(v);
        }
    }
} 
void bfs(int u){
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            if(!fa2[v]){
                fa2[v]=u;
                write1(u),write2(v);
                q.push(v);  //再加入一个新点  
            }
        }
    }
}
signed main(){
    n=read(),m=read();
    while(m--){
        int u=read(),v=read();
        g[u].push_back(v),g[v].push_back(u);
    }
    fa1[1]=fa2[1]=n+1;  //免得之后再来处理  
    dfs(1),bfs(1);
    return 0;
}//在寂寞的时分 无论飞向何方