洛谷2746 校园网Network of Schools

题意

一个有向图，求：

1. 至少选多少个起点才可以遍历整个图
2. 至少加几条边，能满足从任意一个点出发都能遍历整张图

其中点数 $N\le 100$ 。

题解

显然可以先缩点，然后对题意进行转化：

1. 入度为 $0$ 的点的个数
2. 加最少的边，让整张图成一个环

问题 $1$ 很显然，对于问题 $2$ ，可以把所有入度为 $0$ 和出度为 $0$ 的节点相连，所以答案即为两者的较大值。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int from,next,to;
} edge[10005];
stack <int> s;
bool in[105],out[105];
int cnt,head[105],n,m,a,ans1,ans2;
int dfsord,scnt,scc[105],id[105],low[105];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].from=u;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x)
{
    id[x]=low[x]=++dfsord;
    s.push(x);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (!id[y])
        {
            dfs(y);
            low[x]=min(low[x],low[y]);
        }
        else if (!scc[y]) low[x]=min(low[x],id[y]);
    }
    if (id[x]==low[x])
    {
        scnt++;
        while (!s.empty())
        {
            int t=s.top(); s.pop();
            scc[t]=scnt;
            if (t==x) break;
        }
    }
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        for (;;)
        {
            a=read();
            if (!a) break;
            add(i,a);
        }
    }
    for (int i=1;i<=n;i++)
    {
        if (id[i]) continue;
        dfs(i);
    }
    for (int i=1;i<=cnt;i++)
    {
        int x=edge[i].from,y=edge[i].to;
        if (scc[x]==scc[y]) continue;
        in[scc[y]]=1;
        out[scc[x]]=1;
    }
    for (int i=1;i<=scnt;i++)
    {
        ans1+=(!in[i]);
        ans2+=(!out[i]);
    }
    ans2=max(ans2,ans1);
    printf(scnt==1 ? "1\n0" : "%d\n%d",ans1,ans2);
    return 0;
}