强连通分量+缩点+拓扑DP

分析

① 若 |P|=1，则只有一个起点，并且这个起点能走到所有点，只要将每一个终点都向这个起点连一条边，那么对于图中任意一点，都可以到达所有点，新加的边数为 |Q|。

② 若 |P|≥2，则 |Q|≥|P|≥2，此时至少存在 2 个起点 p1,p2，2 个终点 q1,q2，满足 p1能走到 q1，p2 能走到q2。（反证法：如果不存在两个起点能走到不同的终点，则所有的起点一定只能走到同一个终点，而终点至少有两个，发生矛盾，假设不成立）

那么我们可以从 q1向p2新连一条边，那么此时起点和终点的个数都会减少一个（p2不再是起点,q1不再是终点），因此只要以这种方式，连接新边 |P|−1条，则 |P'|=1，而 |Q'|=|Q|−(|P|−1)，由 ① 得，当 |P'|=1时，需要再连 |Q'|条新边，那么总添加的新边数量为 |P|−1+|Q|−(|P|−1)=|Q|

2.|Q|≤|P|

与情况 11 对称，此时答案为 |P|。

综上所述，scc_cnt>1 时，问题二的答案为 max(|P|,|Q|)即 max(src,des))。

AC代码:

#include<bits/stdc++.h>
#pragma GCC opitimize(2)
using namespace std;
const int N=1e5+5;
namespace Read
{
    inline int read()
    {
        int s=0,f=1; char ch=getchar();
        while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
        while(isdigit(ch)) s=s*10+(ch^48),ch=getchar();
        return s*f;
    }
    inline void write(int x)
    {
        if(x<0) putchar('-'),x=-x;
        if(x>9) write(x/10);
        putchar(x%10+'0');
    }
}using namespace Read;
namespace Gragh
{
    int n,m,tot=0;
    int head[N],Next[N<<1],des[N<<1];
    inline void add(int a,int b)
    {
        Next[++tot]=head[a]; des[tot]=b; 
        head[a]=tot;
    }
}using namespace Gragh;
namespace Tarjan
{
    int num=0,cnt=0;
    int low[N],dfn[N],ins[N],c[N];
    stack<int> stk;
    vector<int> scc[N];
    void tarjan(int x)
    {
        low[x]=dfn[x]=++num;
        stk.push(x); ins[x]=1;
        for(int i=head[x]; i; i=Next[i])
        {
            int y=des[i];
            if(!dfn[y])
            {
                tarjan(y);
                low[x]=min(low[x],low[y]);
            } 
            else if(ins[y]) low[x]=min(low[x],dfn[y]);
        }
        if(dfn[x]==low[x])
        {
            int y; cnt++;
            do
            {
                y=stk.top(); stk.pop(); ins[y]=0;
                c[y]=cnt; scc[cnt].push_back(y);
            }while(y!=x);
        }
    }
}using namespace Tarjan;
namespace ContractionPoint
{
    int tot2=0;
    int head2[N],Next2[N<<1],des2[N<<1],in[N],out[N];
    inline void add2(int a,int b)
    {
        Next2[++tot2]=head2[a]; des2[tot2]=b; 
        head2[a]=tot2; in[b]++; out[a]++; 
    }
}using namespace ContractionPoint;  
int main()
{
    n=read();
    for(int i=1; i<=n; i++)
    {
        while(true)
        {
            int x=read();
            if(!x) break;
            add(i,x);
        }
    } 
    for(int i=1; i<=n; i++)
        if(!dfn[i]) tarjan(i);
    for(int x=1; x<=n; x++)
        for(int i=head[x]; i; i=Next[i])
        {
            int y=des[i];
            if(c[x]!=c[y]) add2(c[x],c[y]);
        } 
    int ans1=0,ans2=0;
    for(int i=1; i<=cnt; i++)
        if(in[i]==0) ans1++;
    for(int i=1; i<=cnt; i++)
        if(out[i]==0) ans2++;
    ans2=max(ans2,ans1);
    if(cnt==1) ans2=0;
    write(ans1),puts(""),write(ans2);
    return 0;
}

注：本题解非原创，转载自https://www.acwing.com/solution/content/4663/