G. Remove Directed Edges
题意：给定有向无环图，要求找出最大满足“条件”的联通分量
条件：对于这个联通分量，任意两点之间有路径
思路：树上DP找出最长链。
注意题目对于入度和出度的要求。
#include <bits/stdc++.h>
const int N = 2e5+100;
using namespace std;
struct node
{
int nex,to;
};
node edge[N];
int head[N],tot,ans=1;
void add(int from,int to)
{
edge[++tot].nex=head[from];
edge[tot].to=to;
head[from]=tot;
}
int dp[N],rd[N],out[N];
void DFS(int now)
{
if(dp[now])
return ;
dp[now]=1;
if(out[now]<2)
return ;
for(int i=head[now];i;i=edge[i].nex)
{
DFS(edge[i].to);
if(rd[edge[i].to]>=2)
dp[now]=dp[now]<(dp[edge[i].to]+1)?(dp[edge[i].to]+1):dp[now];
}
ans=ans<dp[now]?dp[now]:ans;
}
int main()
{
int n,m;
cin>>n>>m;
for(register int i=1,a,b;i<=m;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
rd[b]++;out[a]++;
}
for(int i=1;i<=n;i++)
DFS(i);
cout<<ans<<endl;
return 0;
}
