P3916 图的遍历【反向建边 + DFS】
遍历 反向 DFS
2023-06-13 09:15:39 时间
https://www.luogu.com.cn/problem/P3916
题目描述
给出NN个点，MM条边的有向图，对于每个点vv，求A(v)A(v)表示从点vv出发，能到达的编号最大的点。
输入格式
第1 行，2 个整数N,MN,M。
接下来MM行，每行2个整数U_i,V_iUi,Vi，表示边(U_i,V_i)(Ui,Vi)。点用1, 2,\cdots,N1,2,⋯,N编号。
输出格式
N 个整数A(1),A(2),\cdots,A(N)A(1),A(2),⋯,A(N)。
输入输出样例
输入 #1复制
4 3
1 2
2 4
4 3输出 #1复制
4 4 3 4说明/提示
• 对于60% 的数据，1 \le N . M \le 10^31≤N.M≤103；
• 对于100% 的数据，1 \le N , M \le 10^51≤N,M≤105。
题解：反向建边，再进行搜索。例如题目中，反向建边后是：2->1，4->2，3->4，从大到小开始DFS。（反向建边后，如果遍历该节点连接的边，即能够到达的地方，比如e[4] 里面存储了2，那么2一定能到达4，如果之后遍历3，2，1的时候，一定也不会比4大。关键是从大到小进行了遍历。）这样子如果当前点的ans[ ]有数值了，就说明已经遍历过了，而且肯定比当前要大，就不需要再继续遍历下去。
碎碎念：正常建边，然后跑DFS，一大半样例会TLE，只有我这样子的憨憨才会这样子做。。。
代码思路源于洛谷题解。
#include <bits/stdc++.h>
using namespace std;
int n,m,u,v;
int ans[100050];
vector<int>e[100050];
void dfs(int x, int d)
{
if(ans[x]) return ;
ans[x] = d;
for(int i = 0; i < e[x].size(); i ++)
{
dfs(e[x][i],d);
}
}
int main()
{
scanf("%d%d", &n,&m);
for(int i = 0; i < m; i ++)
{
scanf("%d %d", &u, &v);
e[v].push_back(u);
}
for(int i = n; i >= 1; i --)
{
dfs(i,i);
}
for(int i = 1; i <= n; i ++)
{
if(i == 1) printf("%d",ans[i]);
else printf(" %d",ans[i]);
}
printf("\n");
return 0;
}