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

作者: wjyyy 分类: tarjan,解题报告 发布时间: 2018-06-06 20:14

点击量:31

这个题涉及到有向图中的信息传递,需要用到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
   因为软件是可以通过有向图共享的,所以在环(强连通分量)中,无论给任何一个节点,其他节点都能收到,这时就可以缩点,把它们看作一个点。
缩点详细注解教程
   对于缩点后的一些点,就不是强连通分量,可以当作森林来做,只要每一棵树的根有了软件,这棵树上的节点都有了软件。所以答案就是(缩点后)入度为0的点有多少个。
   第二问,缩点后的森林,如果要互相连接,所有点都要有入度,都要有出度,可以证明:答案是入度和出度的较大值,因为每一个出度为0的点消掉一个(另一棵树上)入度为0的点,要消掉所有出度或入度为0的点,就要连接较大值条边才能满足。
   tip:记得特判当整张图是单独一个强连通分量时,不用连接边。

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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */