题意

输入一个 $n$ 个点，$m$ 条边的有向图。输出每个点能走到的最大的点的数

思路

遍历这个点能走到的地方，找最大值

可以用 DFS 和 BFS 做

代码

BFS

int bfs(int n){
	int mx = 0;
	queue<int> q;
	q.push(n);
	f[n] = 1;
	while (!q.empty()){
		int x = q.front();
		mx = max(mx,x);	// 最大值
		for (int i = 0;i < a[x].size();i++){	// 遍历
			if (!f[a[x][i]]){
				f[a[x][i]] = 1;
				q.push(a[x][i]);
			}
		}
		q.pop();
	}
	return mx;
}

完整版

#include <bits/stdc++.h>
using namespace std;
vector<int> a[1005];
bool f[1005];
int dfs(int n){
	int mx = n;	// 最大值
	f[n] = 1;
	for (int i = 0;i < a[n].size();i++){
		if(!f[a[n][i]])	mx = max(mx,dfs(a[n][i]));	// 如果没被遍历，就遍历并记录最大值
	}
	return mx;
}
int main(int argc, char **argv){
	int n,m;
	cin >> n >> m;
	for (int i = 0;i < m;i++){
		int u,v;
		cin >> u >> v;
		a[u].push_back(v);	// u 指向 v
	}
	for (int i = 1;i <= n;i++){
		printf("%d ",dfs(i));
//		printf("%d ",bfs(i));
		fill(f,f + 1000,0);	// 重置标记数组
	}
	return 0;
}

题目真"简单"

看了图的遍历(正常版),真简单

#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 dfs(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]);//设置最大值
    dfs(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++)//A(n)
 {
  maxn=i;//初始化,一定为 i !!!
  fill(vis+0,vis+N,0);//初始化
  dfs(i);//深度优先
  cout<<maxn<<" ";//输出最大值
 }
 return 0;//完结散花
}

#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<int>g[1001];
int vis[1001];
int maxn=0;
int n,m;
void dfs(int n){
	if(n>maxn){
		maxn=n;
	}
	vis[n]=1;
	for(int i=0;i<g[n].size();i++){
		if(vis[g[n][i]]!=1){
		dfs(g[n][i]);	
		}
	}
}
int main(){
	cin>>n>>m;
	int x,y;
    for(int i=1;i<=m;i++){
    	cin>>x>>y;
    	g[x].push_back(y);
	}
	for(int i=1;i<=n;i++){
		dfs(i);
		cout<<maxn<<" ";
		maxn=0;
		fill(vis,vis+n+1,0);
	}
}

Copy

#include<bits/stdc++.h>
using namespace std;
const int mx=1e5+10;
int n,m;
int ax=0;
vector<int> g[mx]={};
bool vst[mx]={};
void dfs(int u){
	ax=max(ax,u);
	if(vst[u]) return;
	vst[u]=true;
	int t=g[u].size();
	for(int i=0;i<t;i++){
		if(!vst[g[u][i]]) dfs(g[u][i]);
		vst[g[u][i]]=true;
	}
}
/*void bfs(int v){

}*/
int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
	}
	for(int i=1;i<=n;i++){
		fill(vst,vst+mx,false);
		ax=0;
		dfs(i);
		cout<<ax<<' ';
	}
	return 0;
}

看完下面的题

同志们这是真的简单啊

题目真"简单"

看了图的遍历(正常版),真简单

#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 dfs(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]);//设置最大值
    dfs(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++)//A(n)
 {
  maxn=i;//初始化,一定为 i !!!
  fill(vis+0,vis+N,0);//初始化
  dfs(i);//深度优先
  cout<<maxn<<" ";//输出最大值
 }
 return 0;//完结散花
}