DPまとめコンテスト G - Longest Path

G - Longest Path

概要

頂点辺のDAGの最長パスの長さを出力せよ。

制約

方針①

まず、トポロジカルソートを行い、頂点の移動順を求める。
トポロジカルソートは帰りがけ順DFSの出力の逆順とする。

次に、 : トポロジカルソートで頂点より後ろのパスの最大長 とし、DPする。
これは、トポロジカルソートされた頂点を逆順で見てゆき、頂点に対して、その頂点が出発点となる各辺の行先点について、が最も大きいものに1を足して更新してゆけばよい。

解答①

Submission #3959327 - Educational DP Contest / DP まとめコンテスト

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
// トポロジカルソート
int n, m;
const int max_n = 1e5 + 10;
 
vector<int> g[max_n];
bool used[max_n];
 
vector<int> v;
 
void dfs(int u){
	if(used[u]) return;
	used[u] = true;
	for(int i: g[u]) dfs(i);
	//帰りがけ順で追加
	v.push_back(u);
}
 
void tsort(){
	for(int i = 0; i < n; i++) dfs(i);
	reverse(v.begin(), v.end());
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> n >> m;
	rep(i, m){
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		g[x].push_back(y);
	}
 
	tsort();
	reverse(v.begin(), v.end());
 
	// cout << "tsort--";
	// rep(i, n) cout << " " << v[i];
	// cout << endl;
 
	// dp[i] : トポロジカルソートで頂点iより後ろのパスの最大長
	vector<int> dp(n, 0);
	int ans = 0;
	for(int i: v){
		for(int u : g[i]){
			// cout << i << " " << u << " " << dp[i] << " " << (dp[u]+1) << endl;
			dp[i] = max(dp[i], dp[u] + 1);
		}
		ans = max(ans, dp[i]);
	}
 
	cout << ans << endl;
}

方針②

上記更新をメモ化再帰で行う。（実はトポロジカルソートは必要ない）

解答②

Submission #3959330 - Educational DP Contest / DP まとめコンテスト

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int max_n = 1e5 + 10;
int n, m;
vector<int> g[max_n];
int d[max_n];
 
int dfs(int x){
	if(d[x] > 0) return d[x];
	int mx = 0;
	rep(i, g[x].size()){
		mx = max(mx, dfs(g[x][i]) + 1);
	}
 
	d[x] = mx;
	return mx;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> n >> m;
	rep(i, m){
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		g[x].push_back(y);
	}
 
	rep(i, n) d[i] = 0;
 
	int ans = 0;
	rep(i, n){
		if(d[i] == 0) ans = max(ans, dfs(i));
	}
 
	cout << ans << endl;
}