Atcoder DP Contest pG
題敘
https://atcoder.jp/contests/dp/tasks/dp_g
給一張有向無環圖$G$，求最長路徑大小
想法
直接DFS每個點是從哪些點轉移過來
將答案直接儲存在點上，當已經有答案時直接回傳，就跟DP的概念一樣
定義 $DP[i]$ 表示點 $i$ 為終點時的最長路徑
則有轉移式 $DP[i] = max(DP[k]+1)$，其中 $k$ 表示所有走向點 $i$ 的點
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
struct dot{
int val=0;
vector<int> from;
}dots[100005];
int n,m;
int dfs(int px){
if(dots[px].from.empty())
return dots[px].val=0;
if(dots[px].val)
return dots[px].val;
int res=0;
for(auto i: dots[px].from){
res=max(res,dfs(i));
}
return dots[px].val=res+1;
}
int main(){
IOS
while(cin>>n>>m){
for(int i=0,a,b ; i<m ; i++){
cin>>a>>b;
dots[b].from.push_back(a);
}
int ans=0;
for(int i=1 ; i<=n ; i++){
ans=max(ans,dfs(i));
}
cout<<ans<<"\n";
}
return 0;
}
|
複雜度
DFS過程會遍歷每個點和邊，且都只會遍歷一次，總複雜度 $O(N+M)$