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