CF1674G题解

ncwzdlsd · 2023-10-25 08:32:52 · 题解

在一个 DAG 上找最长链，且最长链不包含删掉的边。

如何判断最长链上的边是否删掉？对于一个点 i，设 f_i 表示以它为起点的符合条件的最长链长度，如果它的出度小于 2，则它的这条入边一定被删去，此时无法继续转移，f_i=1。而对于出度大于 1 的点，再判断它所能到达的点的入度，如果入度小于 2 则这条边会被删去，也不能转移。

注意转移要记忆化，如果以该点为起点的最长链长度已经计算过了就不用再算一遍了。

代码如下：

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

const int maxn=2e5+5;
struct edge{int to,nxt;}e[maxn];
int head[maxn],f[maxn],in[maxn],out[maxn],cnt;

void add(int x,int y){e[++cnt]={y,head[x]},head[x]=cnt;}

void dfs(int x,int fa)
{
    if(f[x]) return;
    f[x]=1;
    if(out[x]<2) return;
    for(int i=head[x];i;i=e[i].nxt)
    {
        if(e[i].to==fa) continue;
        dfs(e[i].to,x);
        if(in[e[i].to]>1) f[x]=max(f[x],f[e[i].to]+1);
    }
}

int main()
{
    int n,m;cin>>n>>m;
    for(int i=1,u,v;i<=m;i++) cin>>u>>v,add(u,v),in[v]++,out[u]++;
    for(int i=1;i<=n;i++) dfs(i,0);
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,f[i]);
    cout<<ans;
    return 0;
}