题意:

输入一个有向图,n个点,m条有向边

输出A(i)能到达到数字最大的点,1≤i≤n

思路:

采用反向建图的方法

如:1到2有条1到2的有向边,存储时要存1到2有条2到1的有向边

解析:

题意是每个A(i)依次找

所以代码:

#include<iostream>
#include<vector>
using namespace std;
const int N=114514;
vector<int >g[N];
bool vis[N]={0};
int n,m,maxn=0;
void fun(int x)
{
	if(!vis[x])
	{
		vis[x]=1;
		for(int i=0;i<g[x].size();i++)
		{
			if(!vis[g[x][i]])
			{
				maxn=max(maxn,g[x][i]);
				fun(g[x][i]);
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
	{
		maxn=i;
		fill(vis+0,vis+N,0);
		fun(i);
		cout<<maxn<<" ";
	}
	return 0;
}

如果你只是复制上面代码去提交而没看下一面的内容,估计90分,TLE了

因为上面的代码时间复杂度是O(n²),所以TLE

我们换一种思路

不如从最大的(n)开始反着找,把所有走过的点的最大的点存起来

模拟:

输入:
4 3
1 2
2 4
4 3

图:
1-->2
    ↓
3<--4

反向图:
1<--2
    ↑
3-->4

标记数组:
0<--0
    ↑
0-->0

从4开始(最大的),循环到1:

4:
标记数组:
4<--4
    ↑
0-->4

3:
标记数组:
4<--4
    ↑
3-->4

2:
标记数组:
4<--4
    ↑
3-->4

1:
标记数组:
4<--4
    ↑
3-->4

输出:
4 4 3 4

代码:

#include<iostream>
#include<vector>
using namespace std;
const int N=114514;
vector<int >g[N];//反向建图
int b[N]={0};//存储数组
int n,m;
void dfs(int x,int y)//深度优先
{
	b[x]=y;//记录
	for(int i=0;i<g[x].size();i++)
	{
		if(!b[g[x][i]])//没有记录时
		{
			dfs(g[x][i],y);//深度优先
		}
	}
}
int main()
{
	cin>>n>>m;//输入
	for(int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;//输入
		g[v].push_back(u);//添加反向边
	}
	for(int i=n;i>=1;i--)
	{
		if(!b[i])//没有记录时
		{
			b[i]=i;//记录
			dfs(i,i);//深度优先
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<b[i]<<" ";//输出
	}
	return 0;//完结散花
}

#include <bits/stdc++.h>
using namespace std;
int n,m,ans[100005];
vector<int> g[100005];
void dfs(int x,int st){
	if(ans[x]) return ;
	ans[x]=st;
	for(auto v:g[x]){
		if(!ans[v]) dfs(v,st);
	}
    return ;
}
int main(){
	cin>>n>>m;
	for(int i=1,a,b;i<=m;i++){
		cin>>a>>b;
		g[b].push_back(a);//反向建图 
	}
	for(int i=n;i>=1;i--) dfs(i,i);
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}