P3916 圖的遍歷
題目來源-洛谷

題意

有向圖中，找出每個節點能訪問到的最大的節點

思路

• 每個節點的最大節點，不是最長距離，如果是每個節點都用dfs去找最大值，顯然1e6*1e6 超時了，只能60分
• 從第一個節點開始遍歷，要超時，逆著思路想，求最大節點，那么從最大的節點開始遍歷，逆著看哪些點能到達該節點，立刻標記，且從大的節點來看，后面的節點不可能有比該節點更大的點（哪怕有，也是被訪問的-比當前更大的節點），因此只需要標記走過的節點，就可以不必再重復遍歷，節省時間開銷
• 因此存圖時需要逆向存

數據約束

注意數組長度即可

參考代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
void dfs(int k,int maxk);//從節點K開始搜索 
int m,n;//n個點m條邊 
vector<int> p[MAXN];//鄰接表存圖 
bool f[MAXN] = {false};
int ans[MAXN] ;//存結果 
int main(){ cin>>n>>m;int x,y;for(int i=0;i<m;i++){cin>>x>>y; //x 能到 y p[y].push_back(x);//反向存圖 } //	查看儲存的數據是否正確 
//	for(int i=1;i<=n;i++){
//		for(int j=0;j<p[i].size();j++){
//			cout<<p[i][j]<<" "; 
//		} 
//		cout<<endl;
//	}for(int i=n;i>0;i--){dfs(i,i) ;//從最大的點開始搜索 } for(int i=1;i<=n;i++){cout<<ans[i]<<" ";}return 0;
}
void dfs(int k,int maxk){if(f[k]) return;ans[k] = maxk;f[k] = true;//如果此處不標記，但是是第一個遍歷到節點就必須記得處理 for(int i=0;i<p[k].size();i++){if(!f[p[k][i]]){ //沒被訪問過則訪問 dfs(p[k][i],maxk);//	f[p[k][i]] = true;//在開頭賦值的地方標記后就不用重復標記 }}return ;
}