【洛谷P3916】图的遍历

题目大意：给定一个 N 个点，M 条边的有向图，求每个点能够到达的节点的最大编号是多少。

题解：因为题中所给图不一定是一个 DAG，因此无法进行按照拓扑序来动态规划，需要另辟蹊径。由于求的是每个节点能够到达的最大编号，因此可以考虑反向建图，并依次从大到小枚举节点编号，将该节点能够到达的节点修改为当前节点的编号，算法正确性显然。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+10;

inline int read(){

	int x=0,f=1;char ch;

	do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

	do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

	return f*x;

}

struct node{

	int nxt,to;

}e[maxn];

int tot=1,head[maxn];

int n,m,dp[maxn];

inline void add_edge(int from,int to){

	e[++tot]=node{head[from],to},head[from]=tot;

}

void read_and_parse(){

	n=read(),m=read();

	for(int i=1,from,to;i<=m;i++){

		from=read(),to=read();

		add_edge(to,from);

	}

}

void bfs(int idx){

	queue<int> q;

	q.push(idx);

	while(q.size()){

		int u=q.front();q.pop();

		dp[u]=idx;

		for(int i=head[u];i;i=e[i].nxt)if(!dp[e[i].to])q.push(e[i].to);

	}

}

void solve(){

	for(int i=n;i>=1;i--){

		if(dp[i])continue;

		bfs(i);

	}

	for(int i=1;i<=n;i++)printf("%d%c",dp[i],i==n?'\n':' ');

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【洛谷P3916】图的遍历

最新文章

热门文章