【洛谷P2746】[USACO5.3]校园网Network of Schools

校园网Network of Schools

第一问：Tarjan缩点，搞出每一个连通块，入度为零的连通块是需要必须接受新软件副本的，统计数量即可

第二问：要让整个图构成一个环，显然要将入度为零点和出度为零点都消灭，ans=max(入度为零点的数量，出度为零点的数量)

#include<iostream>

#include<cstring>

#include<cstdio>

#define N 110

int n,Head[N],Enum,stack[N],top,ans1,ans2;

int dfn[N],cnt,low[N],belong[N],num;

bool ins[N],in[N],out[N];

struct NODE{

    int to,next;

} e[N*N];

inline void add(int x,int y){

    e[++Enum].to=y;

    e[Enum].next=Head[x];

    Head[x]=Enum;

}

inline int read(){

    int x=; char c=getchar();

    while(c<''||c>'') c=getchar();

    while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }

    return x;

}

inline void Tarjan(int u){

    dfn[u]=low[u]=++cnt;

    ins[u]=; stack[++top]=u;

    for(int i=Head[u];i;i=e[i].next){

        int v=e[i].to;

        if(!dfn[v]){

            Tarjan(v);

            low[u]=std::min(low[u],low[v]);

        }

        else if(ins[v])

            low[u]=std::min(low[u],dfn[v]);

    }

    if(low[u]==dfn[u]){

        belong[u]=++num;

        while(stack[top]!=u){

            int k=stack[top];

            belong[k]=num;

            ins[k]=;

            top--;

        }

        top--; ins[u]=;

    }

}

int main()

{

    n=read(); int x;

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

        x=read();

        while(x){ add(i,x); x=read(); }

    }

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

     if(!dfn[i]) Tarjan(i);

    if(num==) { printf("%d\n%d\n",,); return ; }

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

     for(int j=Head[i];j;j=e[j].next)

      if(belong[i]!=belong[e[j].to])

          out[belong[i]]=in[belong[e[j].to]]=;

    for(int i=;i<=num;i++){

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

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

    }

    ans2=std::max(ans1,ans2);

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

    return ;

}

双倍经验: P2812