洛谷 P2812 [USACO5.3] Network of Schools 题解【tarjan】

点击量：310

这个题涉及到有向图中的信息传递，需要用到tarjan缩点。

（洛谷数据加强版）

目录

题目背景

浙江省的几所OI强校的神犇发明了一种人工智能，可以AC任何题目，所以他们决定建立一个网络来共享这个软件。但是由于他们脑力劳动过多导致全身无力身体被♂掏♂空，他们来找你帮助他们。

题目描述

共有n所学校（n<=10000）已知他们实现设计好的网络共m条线路，为了保证高速，网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机母鸡，能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机母鸡都可以使别的学校使用上软件。

输入输出格式

输入格式：

第一行一个整数n。

接下来n行每行有若干个整数，用空格空格隔开。

第i-1行的非零整数x，表示从i到x有一条线路。以0作为结束标志。

输出格式：

第一行一个整数表示问题1的答案。

第二行回答问题2.

输入输出样例

输入样例#1：

5

2 0

4 0

5 0

1 0

0

输出样例#1：

2

2

Code：

#include<cstdio>
#include<cstring>
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
struct node
{
    int n;
    node *nxt;
    node(int n)
    {
        this->n=n;
        nxt=NULL;
    }
    node(){nxt=NULL;}
};
node head[10020],*tail[10020];
int n;
int dfn[10020],low[10020],cnt=0;
int s[10020],top=0;
bool in[10020];
int belong[10020],num=0;
void dfs(int x)//tarjan
{
    dfn[x]=++cnt;
    low[x]=dfn[x];
    s[++top]=x;
    in[x]=true;
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(!in[p->n]&&dfn[p->n])
            continue;
        if(dfn[p->n])
        {
            low[x]=min(low[x],low[p->n]);
            continue;
        }
        dfs(p->n);
        low[x]=min(low[x],low[p->n]);
    }
    if(low[x]==dfn[x])
    {
        top++;
        num++;
        do
        {
            top--;
            belong[s[top]]=num;
            in[s[top]]=false;
        }while(s[top]!=x);
        top--;
    }
    return;
}
int indeg[10020],outdeg[10020];
void build()
{
    node Head[10020],*Tail[10020];
    for(int i=1;i<=num;i++)
        Tail[i]=&Head[i];
    node *p;
    for(int i=1;i<=n;i++)
    {
        p=&head[i];
        while(p->nxt!=NULL)
        {
            p=p->nxt;
            if(belong[i]!=belong[p->n])//belong存的是第几个强连通分量
            {
                Tail[belong[i]]->nxt=new node(belong[p->n]);
                Tail[belong[i]]=Tail[belong[i]]->nxt;

                outdeg[belong[i]]++;
                indeg[belong[p->n]]++;
            }
        }
    }
}
int main()
{
    memset(in,false,sizeof(in));
    memset(dfn,0,sizeof(dfn));
    memset(indeg,0,sizeof(indeg));
    memset(outdeg,0,sizeof(outdeg));
    int u;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        tail[i]=&head[i];
        scanf("%d",&u);
        while(u!=0)
        {
            tail[i]->nxt=new node(u);
            tail[i]=tail[i]->nxt;
            scanf("%d",&u);
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            dfs(i);
    build();
    int sum1=0;
    for(int i=1;i<=num;i++)//求入度和出度
    {
        if(indeg[i]==0)
            sum++;
        if(outdeg[i]==0)
            sum1++;
    }
    if(num==1)
    {
        printf("1\n0\n");
        return 0;
    }
    printf("%d\n%d\n",sum,max(sum,sum1));
    return 0;
}