每日一题 第五期 洛谷 图的遍历

图的遍历

题目描述

给出 $N$ 个点，$M$ 条边的有向图，对于每个点 $v$，求 $A(v)$ 表示从点 $v$ 出发，能到达的编号最大的点。

输入格式

第 $1$ 行 $2$ 个整数 $N,M$，表示点数和边数。

接下来 $M$ 行，每行 $2$ 个整数 $U_i,V_i$，表示边 $(U_i,V_i)$。点用 $1,2,\dots ,N$ 编号。

输出格式

一行 $N$ 个整数 $A(1),A(2),\dots ,A(N)$。

样例 #1

样例输入 #1

4 3
1 2
2 4
4 3

样例输出 #1

4 4 3 4

提示

• 对于 $60\%$ 的数据，$1\le N,M\le 10^3$。
• 对于 $100\%$ 的数据，$1\le N,M\le 10^5$。

常规思路容易超时就是正向DFS，下面是错误的实例：

#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<queue>
#include<string>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<numeric>
#define endl '\n'
using namespace std;

typedef long long ll;
typedef pair<int, int>PII;
const int N=3e5+10;
const int MOD=998244353;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e4 + 10;

vector<int>v[10010];
int n, m;
bitset<N> st;
int maxs;
void dfs(int u)
{
	maxs = max(u, maxs);
	if(!v[u].size())
	{
		cout << maxs << " ";
		return ;
	}
	else 
	{
		sort(v[u].begin(), v[u].end());
		for(int i = 0; i < v[u].size(); i ++)
		{
		    st[v[u][i]] = 1;
//			maxs = max(v[u][i], maxs);
			dfs(v[u][i]);
		}
	}
	
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		int x, y;

		cin >> x >> y;
		v[x].push_back(y);
	}
	for(int i = 1; i <= n; i ++)
	{
		maxs = 0;
		st.reset();
		dfs(i);
	}
//	dfs(1);
	return 0;
}

显然该做法超时；

下面给出正确的解法：

我们应该反向进行遍历，因为这样我们就可以直接从最大的开始筛选了

AC代码：

#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<queue>
#include<string>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<numeric>
#define endl '\n'
using namespace std;

typedef long long ll;
typedef pair<int, int>PII;
const int N=3e5+10;
const int MOD=998244353;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e4 + 10;

vector<int> v[N];
int a[N];
bitset<N> s;
int n, m ;

void dfs(int u, int c)
{
	if(a[u]) return ;// 说明u点的最大值已经找到了
	a[u] = c;//给其赋值
	for(int i = 0; i < v[u].size() ; i ++)
	{
		dfs(v[u][i], c);
	}
}
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		int x, y;
		cin >> x >> y;
		v[y].push_back(x);// 反向存图看能到哪一个点
	}
	//反向遍历看大的点能到哪一个点，该大的点即为那个点的最大值
	for(int i = n; i >= 1; i --) dfs(i , i);
	for(int i = 1; i <= n; i ++) cout << a[i] << " ";
	return 0;
}