P2746 [USACO5.3]校园网Network of Schools

传送门

把所有学校的关系构成一个图，显然一个强联通分量的所有学校只要有一个有新软件，其他学校也都会有

考虑缩点，发现入度为 0 的块一定要给，因为没有其他人给它

入度不为 0 的块一定有其他人给，我们只要给 能给它的块 提供软件就可以了

所以就是入度为 0 的块一定给，不为 0 的块一定不用给

子任务A就是求出入度为 0 的块的数量

然后考虑子任务B

显然出度为 0 的块一定要连边出去，入度为 0 的块也一定要有边连过来

所以出度为 0 的块连给谁呢，当然给入度为 0 的块

所以就是求 出度为 0 的块数量 和 入度为 0 的块的数量的较大值

当然别忘了特判整个图本身就是联通块的情况

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=;

int n;

int fir[N],from[N<<],to[N<<],cntt;

inline void add(int &a,int &b)

{

    from[++cntt]=fir[a];

    fir[a]=cntt; to[cntt]=b;

}

//Tarjan模板

int dfs_clock,dfn[N],low[N],st[N],Top;

int bel[N],tot;//存每个点属于哪个块

void Tarjan(int x)

{

    dfn[x]=low[x]=++dfs_clock; st[++Top]=x;

    for(int i=fir[x];i;i=from[i])

    {

        int &v=to[i];

        if(!dfn[v]) Tarjan(v),low[x]=min(low[x],low[v]);

        else if(!bel[v]) low[x]=min(low[x],dfn[v]);

    }

    if(low[x]==dfn[x])

    {

        tot++;

        while(st[Top]!=x) { bel[st[Top]]=tot; Top--; }

        bel[x]=tot; Top--;

    }

}

int in[N],out[N],ans1,ans2;//入度，出度，入度为0的数量和出度为0的数量

inline void build()//计算in,ouw,ans1,ans2

{

    for(int i=;i<=n;i++)

        for(int j=fir[i];j;j=from[j])

        {

            int &t=to[j];

            if(bel[i]==bel[t]) continue;//同块内不考虑

            out[bel[i]]++; in[bel[t]]++;

        }

    for(int i=;i<=tot;i++)

    {

        if(!in[i]) ans1++;

        if(!out[i]) ans2++;

    }

}

int main()

{

    int a;

    n=read();

    for(int i=;i<=n;i++)

    {

        a=read();

        while(a) add(i,a),a=read();

    }

    for(int i=;i<=n;i++) if(!bel[i]) Tarjan(i);

    build();

    if(tot==) printf("%d\n%d",,);//特判

    else printf("%d\n%d",ans1,max(ans1,ans2));

    return ;

}