洛谷 P3916 图的遍历
题目描述
给出N个点,M条边的有向图,对于每个点v,求A(v)表示从点v出发,能到达的编号最大的点。
输入格式
第1 行,2 个整数N,M。
接下来M行,每行2个整数Ui?,Vi?,表示边(Ui?,Vi?)。点用1,2,?,N编号。
输出格式
N 个整数A(1),A(2),?,A(N)。
输入输出样例
输入 #14 3 1 2 2 4 4 3输出 #1
4 4 3 4
说明/提示
? 对于60% 的数据,1≤N.M≤10^3;
? 对于100% 的数据,1≤N,M≤10^5。
搭建反向边
做一下图的搭建,dfs,bfs笔记
记录一下for写的bfs
#includegragh#include #include #include using namespace std; struct edge { int to; //int val; int next; }e[100005]; int link[100005],ltp,ans[100005],q[100005]; bool vis[100005]; void insert(int x,int y) { e[++ltp].to=y; e[ltp].next=link[x]; link[x]=ltp; } void dfs(int st,int val) { vis[st]=1; ans[st]=val; for(int i=link[st];i;i=e[i].next) if(!vis[e[i].to]) dfs(e[i].to,val); } void bfs(int st,int val) { int l=1; q[l]=st; vis[st]=1; for(int i=1;i<=l;i++) for(int j=link[q[i]];j;j=e[j].next) if(!vis[e[j].to]) { q[++l]=e[j].to; vis[e[j].to]=1; } for(int i=1;i<=l;i++) ans[q[i]]=val; } int main() { int m,a; int x,y; scanf("%d%d",&m,&a); for(int i=1;i<=a;i++) { scanf("%d%d",&x,&y); insert(y,x); } /* dfs: for(int i=m;i>=1;i--) if(!vis[i]) dfs(i,i); */ for(int i=m;i>=1;i--) if(!vis[i]) bfs(i,i); for(int i=1;i<=m;i++) { if(i>1) printf(" "); printf("%d",ans[i]); } return 0; }