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

时间:2024-03-16 16:04:41

图的遍历

题目描述

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

输入格式

1 1 1 2 2 2 个整数 N , M N,M N,M,表示点数和边数。

接下来 M M M 行,每行 2 2 2 个整数 U i , V i U_i,V_i Ui,Vi,表示边 ( U i , V i ) (U_i,V_i) (Ui,Vi)。点用 1 , 2 , … , N 1,2,\dots,N 1,2,,N 编号。

输出格式

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

样例 #1

样例输入 #1

4 3
1 2
2 4
4 3

样例输出 #1

4 4 3 4

提示

  • 对于 60 % 60\% 60% 的数据, 1 ≤ N , M ≤ 1 0 3 1 \leq N,M \leq 10^3 1N,M103
  • 对于 100 % 100\% 100% 的数据, 1 ≤ N , M ≤ 1 0 5 1 \leq N,M \leq 10^5 1N,M105

常规思路容易超时就是正向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;
}