[YsOI2023] 广度优先遍历 逆向输出路径(分层建树拓扑序. LCA)

今天的模板测试是无向图上的广度优先遍历，【数据删除】马上写好了代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 using namespace std;
 8 const int maxn = 100005;
 9 vector<int> G[maxn];
10 queue<int> q;
11 int pa[maxn];
12 int main()
13 {
14     int n, m;
15     cin >> n >> m;
16     for (int i = 1; i <= m; ++i)
17     {
18         int u, v;
19         cin >> u >> v;
20         G[u].push_back(v);
21         G[v].push_back(u);
22     }
23     memset(pa, -1, sizeof pa);
24     q.push(1);
25     pa[1] = 0;
26     while (!q.empty())
27     {
28         int u = q.front();
29         q.pop();
30         for (auto v : G[u])
31         {
32             if (pa[v] != -1)
33                 continue;
34             pa[v] = u;
35             q.push(v);
36         }
37     }
38     for (int i = 1; i <= n; ++i)
39     {
40         cout << pa[i];
41         if (i != n)
42             cout << " ";
43     }
44     cout << endl;
45     return 0;
46 }

如你所见，这份代码会输入一个 $n$ 个点 $m$ 条边的无向图，并且求出这张图以 $1$ 为根的一棵“广度优先遍历树”，最后输出所有点的父亲节点编号。

不过值得注意的是，这棵“广度优先遍历树”的具体形态和“边的输入顺序”有关，也就是说，不同的输入顺序可能会得到不同的父亲节点编号。

现在【数据删除】告诉了你 $n,m$、这 $m$ 条边以及在某个“边输入顺序”情况下他的代码的输出，你需要还原出这个“边输入顺序”。如果有多种边输入顺序对应的都是这样的输出，你**只需要输出其中任意一种**即可。

特别的，保证有解，且无向图连通，无自环（但是有可能有重边）。

输入格式

第一行两个正整数 $n,m$ 分别表示无向图的点数和边数。

接下来 $m$ 行每行两个整数 $u,v$ 表示存在 $u$ 与 $v$ 之间存在一条无向边。

最后一行 $n$ 个整数表示【数据删除】代码的输出。（由题意可知他输出的是某个“边输入顺序”情况下他得到的“广度优先遍历树”中 $1\sim n$ 这些节点的父亲节点编号）

输出格式

输出包含 $m$ 行，每行两个整数 $u,v$ 表示 $u$ 和 $v$ 之间存在一条无向边，你的输出顺序表示你给出的“边输入顺序”。

请注意，你需要保证如果输入给出的图中 $u,v$ 间连了 $k$ 条边，那么你给出的图中 $u,v$ 间也要连有 $k$ 条边。

如果有多种“边输入顺序”合法，**输出其中任意一种都会被判断为正确**。另外，由于是无向边，所以你输出的**一条边两个点的排列顺序对答案判定没有影响**。

输入输出样例

4 4
2 1
1 3
2 4
4 3
0 1 1 3

1 3
3 4
1 2
2 4

8 9
7 8
6 1
5 4
7 1
4 1
3 7
2 6
7 5
2 4
0 6 7 1 4 1 1 7

6 2
7 3
4 5
1 6
7 8
1 4
1 7
2 4
5 7

说明/提示

样例 1 解释

直接运行【数据删除】的代码即可。

如果不改变边输入顺序，将下面数据输入【数据删除】的代码：

4 4
2 1
1 3
2 4
4 3

他的代码跑出来结果如下：

0 1 1 2

如果按照样例 1 输出给出的顺序，即，将下面数据输入他的代码：

4 4
1 3
3 4
1 2
2 4

输出为：

0 1 1 3

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,p[N],dist[N],in[N];
vector<int>vec[N],dag[N];
map<pair<int,int>,int>mp;
void fake_spfa()
{
    queue<int>que;
    memset(dist,0x3f,sizeof dist);
    que.push(1),dist[1]=0;
    while(!que.empty()){
        int now=que.front(); que.pop();
        for(auto i:vec[now]){
            if(dist[i]>dist[now]+1){
                dist[i]=dist[now]+1;
                que.push(i);
            }
        }
    }
}
void topsort()
{
    queue<int>que;
    for(int i=1;i<=n;i++) if(!in[i]) que.push(i);
    while(!que.empty()){
        int now=que.front(); que.pop();
        if(now!=1){
            int num=mp[make_pair(now,p[now])];
            while(num--) cout<<now<<" "<<p[now]<<endl;
            mp[make_pair(now,p[now])]=mp[make_pair(p[now],now)]=0;
        }
        for(auto u:dag[now]){
            in[v]--;
            if(in[v]==0) que.push(v);
        }
    }
}
int main()
{
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        mp[make_pair(a,b)]++,mp[make_pair(b,a)]++;
        vec[a].push_back(b),vec[b].push_back(a);
    }
    for(int i=1;i<=n;i++) cin>>p[i];
    fake_spfa();
    for(int u=1;u<=n;u++)
        for(auto v:vec[u]){
            if(dist[v]==dist[u]-1&&v!=p[u]){
                dag[p[u]].push_back(v);
                in[v]++;
            }
            dag[u].push_back(p[u]);
            in[p[u]]++;
        }
    topsort();
    for(int u=1;u<=n;u++)
        for(auto v:vec[u]){
            int num=mp[make_pair(u,v)];
            while(num--) cout<<u<<" "<<v<<endl;
            mp[make_pair(u,v)]=mp[make_pair(v,u)]=0;
        }
    return 0;
}