[AtCoder] Educational DP Contest G – Longest Path
問題
方針
トポロジカルソートを利用するみたいです。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N, M; cin >> N >> M; int x[M], y[M]; vector<int> adj[N]; for (int i = 0; i < M; i++) { cin >> x[i] >> y[i]; x[i]--; y[i]--; adj[x[i]].push_back(y[i]); } int indeg[N]{}; int flag[N]{}; for (int i = 0; i < N; i++) { for (int j = 0; j < adj[i].size(); j++) { int u = adj[i][j]; indeg[u]++; } } deque<int> q; vector<int> id; for (int i = 0; i < N; i++) { if (indeg[i] == 0 && flag[i] == 0) { q.push_back(i); while (!q.empty()) { int u = q.front(); id.push_back(u); q.pop_front(); flag[u] = 1; for (int j = 0; j < adj[u].size(); j++) { int v = adj[u][j]; indeg[v]--; if (indeg[v] == 0 && flag[v] == 0) { flag[v] = 1; q.push_back(v); } } } } } int ans = 0; int dp[N]{}; reverse(id.begin(), id.end()); for (int i : id) { for (int j = 0; j < adj[i].size(); j++) { dp[i] = max(dp[i], dp[adj[i][j]] + 1); } ans = max(ans, dp[i]); } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません