kuangbin专题-连通图A - Network of Schools

这道题的意思是就是

问题

1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。

2：至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。

其实问题1就是问，这个图的支配集有多少？？？解决这个问题非常简单，把图缩点后，找到有多少个入度为0的点，就是支配集。一个支配内，所有点可能不是强连通的，但是都可以通过这个点到达。

而问题二其实更加简单，我们只需要把入读为0的点和出度为0的点的数目取一个最大值即可，至于问什么，很简单，我们可以把出度为0的点连接到入度为0的点上面去，这样就保证图的强连通性质。其实这就是求一个图的补图。

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

const int N = ,M=;

int ver[M],Next[M],head[N],dfn[N],low[N];

int sta[N],ins[N],c[N],in_deg[N],out_deg[N];

int n,m,tot,num,top,cnt;

void add(int x,int y)

{

    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;

}

void tarjan(int x)

{

    dfn[x]=low[x]=++num;//序列号+1

    sta[++top]=x,ins[x]=;//入栈，并标记在栈内

    for (int i=head[x]; i; i=Next[i])  //开始访问

        if(!dfn[ver[i]]) //如果没有被处理过

        {

            tarjan(ver[i]);//DFS

            low[x]=min(low[x],low[ver[i]]);

//递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情

        }

        else if (ins[ver[i]])

            low[x]=min(low[x],dfn[ver[i]]);

//比较谁是谁的儿子／父亲。就是链接对应关系

        if (dfn[x] == low[x])//发现是整个强连通分量的子树里面的最小根。

        {

            cnt++;

            int y;

            do

            {

                y=sta[top--],ins[y]=;

                c[y]=cnt;

                //scc[cnt].push_back(y);

            }

            while(x!=y);

        }

}

void solve(int n)

{

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

    {

        if (!dfn[i])

        {

            tarjan(i);

        }

    }

    if (cnt==)

    {

        printf("1\n0\n");

        return;

    }

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

    {

        for (int j=head[u]; j; j=Next[j])

        {

            int v=ver[j];

            if (c[u]==c[v])

            {

                continue;

            }

            out_deg[c[u]]++;

            in_deg[c[v]]++;

        }

    }

    int a,b;

    a=;

    b=;

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

    {

        if (in_deg[i]==)

        {

            a++;

        }

        else if (out_deg[i]==)

        {

            b++;

        }

    }

    printf("%d\n",a);

    printf("%d\n",max(a,b));

}

void init()

{

    memset(dfn,,sizeof(dfn));

    memset(low,,sizeof(low));

    memset(head,,sizeof(head));

    memset(in_deg,,sizeof(in_deg));

    memset(out_deg,,sizeof(out_deg));

    memset(ins,,sizeof(ins));

    top=;

    tot=;

    cnt=;

    num=;

}

int main()

{

    int  tmp;

    while(~scanf("%d",&n))

    {

        init();

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

        {

            while(scanf("%d",&tmp)&&tmp)

            {

                add(i,tmp);

            }

        }

        solve(n);

    }

    return ;

}

巴特西

kuangbin专题-连通图A - Network of Schools

最新文章

热门文章