[백준] 25948 - Islands Tour (c++)

https://www.acmicpc.net/problem/25948

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Seoul Nationalwide Internet Competition 2022 F번

 

문제 요약

정점 N개 간선 M개의 방향 그래프가 주어진다. 그래프에서 각 정점에서 나가는 간선은 최대 한개이다.

한 정점을 두 번 이상 방문하지 않는 최장경로를 구해라.

 

풀이 (M)

• 위상정렬
• DP

그래프의 각 컴포넌트는 사이클을 최대 한개 포함하고 있다. 위상정렬 DP를 통해 사이클을 이루지 않는 간선들만 포함하는 최장경로를 구하고, 남은 간선들에 대해 DFS로 사이클의 크기를 구해서 경로에 붙혀주면 된다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin>>m>>n;
    vector<int> dp(n+1),deg(n+1),adj(n+1);
    for(int i=0,u,v;i<m;i++)
        cin>>u>>v,u++,v++,adj[u]=v,deg[v]++;
    
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(!deg[i])
            q.push(i);

    while(q.size()) {
        int u=q.front();q.pop();
        int v = adj[u];
        if(v==0)
            continue;
        dp[v]=max(dp[v],dp[u]+1);
        if(!--deg[v])
            q.push(v);
    }

    vector<bool> vis(n+1);
    auto dfs = [&](int u,int l,auto f) -> int {
        vis[u]=1;
        int v=adj[u];
        if(vis[v]) {
            dp[u]+=l;
            return l;
        }
        int x =f(v,l+1,f);
        dp[u]+=x;
        return x;
    };  
    for(int i=1;i<=n;i++) {
        if(vis[i])continue;
        if(deg[i])
            dfs(i,1,dfs);
        else
            dp[i]++;
    }
    cout<<*max_element(dp.begin(),dp.end());
}