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

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

 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 }

如你所见，这份代码会输入一个

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

现在【数据删除】告诉了你

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

输入格式

第一行两个正整数

接下来

最后一行

输出格式

输出包含

请注意，你需要保证如果输入给出的图中

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

输入输出样例

输入 #1

输出 #1

输入 #2

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

输出 #2

说明/提示

样例 1 解释

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

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

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

0 1 1 2

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

输出为：

0 1 1 3

思路:

1. 首先，我们用一个 `fake_spfa` 函数对整张图进行广度优先遍历，得到每个节点到根节点的最短距离（即 `dist` 数组）

这是为了确保还原边时能够根据节点之间的距离关系来构建路径。

2. 然后，我们从根节点开始，逐层构建一棵广度优先遍历树，根据每个节点的父亲节点数组，将每个节点连接到其父亲节点上。

在这个过程中，我们构建了一个有向无环图 `dag`，用于后续的拓扑排序。

3. 接下来，我们使用拓扑排序对 `dag` 图进行排序。拓扑排序是一个从入度为0的节点开始，逐层去除入度的过程。

在拓扑排序过程中，我们逆向追溯每条路径，输出路径上的边。

4. 最后，我们再次遍历原始图，输出所有的边。这一步确保我们输出了所有的边，以满足题目的要求。

建图的方式：

- 在建图过程中，我们需要注意题目中提到了重边的情况，即同一对节点可能有多条边。为了应对这种情况，我们可以使用一个 `map` 来记录边的数量，即 `mp`。

每次读取边的信息时，我们将这条边在 `mp` 中的数量加一，以及将边的信息加入 `vec` 数组中。这样就可以处理重边的情况。

- 在构建 `dag` 图时，我们会根据 `dist` 数组来确定边的关系。

对于每个节点 `u`，我们遍历它的邻居节点 `v`，如果 `dist[v] == dist[u] - 1`，且 `v != p[u]`

那么说明边 `(u, v)` 是路径上的一部分，我们将节点 `v` 加入 `dag[p[u]]`，表示 `p[u]` 是节点 `v` 的父亲节点。

#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;
}