图的遍历
题目描述
给出 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 1≤N,M≤103。
- 对于 100 % 100\% 100% 的数据, 1 ≤ N , M ≤ 1 0 5 1 \leq N,M \leq 10^5 1≤N,M≤105。
常规思路容易超时就是正向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;
}