poj 1236 Network of Schools 【强连通图】

题目:poj 1236 Network of Schools 

类似题目hdoj 2767 3836

/*******以下kuang大神的解释,写的很好就不解释了*************************/

强连通分量缩点求入度为0的个数和出度为0的分量个数

题目大意:N(2<N<100)各学校之间有单向的网络,每个学校得到一套软件后,可以通过单向网络向周边的学校传输,问题1:初始至少需要向多少个学校发放软件,使得网络内所有的学校最终都能得到软件。2,至少需要添加几条传输线路(),使任意向一个学校发放软件后,经过若干次传送,网络内所有的学校最终都能得到软件。

 

也就是:

—        给定一个有向图,求:

 

1) 至少要选几个顶点,才能做到从这些顶点出发,可以到达全部顶点

 

2) 至少要加多少条边,才能使得从任何一个顶点出发,都能到达全部顶点

 

—        顶点数<= 100

解题思路:

—        1. 求出所有强连通分量

—        2. 每个强连通分量缩成一点,则形成一个有向无环图DAG

—        3. DAG上面有多少个入度为0的顶点,问题1的答案就是多少

DAG上要加几条边,才能使得DAG变成强连通的,问题2的答案就是多少

加边的方法:

要为每个入度为0的点添加入边,为每个出度为0的点添加出边

假定有 n 个入度为0的点,m个出度为0的点,如何加边?

把所有入度为0的点编号 0,1,2,3,4 ....N -1

每次为一个编号为i的入度0点可达的出度0点,添加一条出边,连到编号为(i+1)%N 的那个出度0,

这需要加n条边

 m <= n,则

加了这n条边后,已经没有入度0点,则问题解决,一共加了n条边

 m > n,则还有m-n个入度0点,则从这些点以外任取一点,和这些点都连上边,即可,这还需加m-n条边。

所以,max(m,n)就是第二个问题的解

此外:当只有一个强连通分支的时候,就是缩点后只有一个点,虽然入度出度为0的都有一个,但是实际上不需要增加清单的项了,所以答案是10


AC代码Hdoj3676:

#include <cstdio>
#include <vector>
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
const int N = 25000;
vector<int> G[N];
int pre[N],lowlink[N],sccno[N],dfs_clock,scc_cnt; //sccno【i】 i所在的scc图的编号
//scc_cnt 联通块的数量
stack<int> s;

void dfs(int u)
{
    pre[u] = lowlink[u] = ++dfs_clock;
    s.push(u);
    for(int i=0; i<G[u].size(); i++)
    {
        int v=G[u][i];
        if(!pre[v])
        {
            dfs(v);
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }
        else if(!sccno[v])
        {
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u])
    {
        scc_cnt++;
        for(;;)
        {
            int x=s.top();
            s.pop();
            sccno[x]=scc_cnt;
            if(x==u)
                break;
        }
    }
}
void find_scc(int n)
{
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0; i<n; i++)
        if(!pre[i]) dfs(i);
}
int in[N],out[N];
int workout(int n) {
    if (scc_cnt == 1)
        return 0;
    memset(in, 0, sizeof(int)*(n+1));
    memset(out, 0, sizeof(int)*(n+1));
    for (int u = 0; u < n; u++) {
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            if (sccno[u] != sccno[v]) {
                in[sccno[v]] += 1;
                out[sccno[u]] += 1;
            }
        }
    }
    int c1 = 0, c2 = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (in[i] == 0) c1 += 1;
        if (out[i] == 0) c2 += 1;
    }
    return max(c1, c2);
}
int main()
{
    int n,m,T;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0;i<m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            G[x-1].push_back(y-1);
        }
        find_scc(n);
        printf("%d\n",workout(n));
        for(int i=0;i<n;i++)
            G[i].clear();
    }
    return 0;
}


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。