首页 > 代码库 > POJ 1236-Network of Schools (图论-有向图强联通tarjan)

POJ 1236-Network of Schools (图论-有向图强联通tarjan)

题目链接:http://poj.org/problem?id=1236

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

解题思路:首先用tarjan求得所有强联通分量,将每个强联通分量看成一个点,这样会得到一个有向无环图DAG, 那么对于问题一只需要要找出DAG图上有多少个入度为0的点,对于问题二需要在DAG图上找出度为0的点的个数, 然后与问题一入度为0的点的个数取最大值, 就是问题二的答案。

需要注意的是只有一个强联通分量的时候, 需要特判一下。

代码如下:

技术分享
#include <stdio.h>#include <vector>#include <string.h>#include <algorithm>using namespace std;const int N = 103;vector<int>vec[N], stk;bool mp[N][N], in_stk[N];int low[N], dfn[N], tot, cou_scc;int belong[N];int n;void tarjan(int u, int f){    dfn[u] = low[u] = tot ++;    stk.push_back(u), in_stk[u] = true;    for(int i=0; i < vec[u].size(); ++ i)    {        int v = vec[u][i];        if(dfn[v] == -1)        {            tarjan(v, u);            low[u] = min(low[u], low[v]);        }        else if(in_stk[v])            low[u] = min(low[u], dfn[v]);    }    if(low[u] == dfn[u])    {        ++ cou_scc;        while(1)        {            int v = stk.back();            stk.pop_back();            in_stk[v] = false;            belong[v] = cou_scc;            if(u == v)                break;        }    }}int main(){    while(scanf("%d", &n) != EOF)    {        memset(mp, false, sizeof(mp));        for(int i=1; i<=n; ++ i)        {            vec[i].clear();            int c;            while(scanf("%d", &c), c)            {                vec[i].push_back(c);                mp[i][c] = true;            }        }        memset(low, -1, sizeof(low));        memset(dfn, -1, sizeof(dfn));        memset(belong, -1, sizeof(belong));        memset(in_stk, false, sizeof(in_stk));        cou_scc = 0, tot = 1;        stk.clear();        for(int i=1; i<=n; ++ i)        {            if(dfn[i] == -1)                tarjan(i, -1);        }        int in[N], out[N];        memset(in, 0, sizeof(in));        memset(out, 0, sizeof(out));        for(int i=1; i<=n; ++ i)        {            for(int j=1; j<=n; ++ j)            {                if(mp[i][j] && belong[i] != belong[j])                {                    ++ in[belong[j]];                    ++ out[belong[i]];                }            }        }        if(cou_scc == 1)        {            printf("1\n0\n");            continue;        }        int x = 0, y = 0;        for(int i=1; i<=cou_scc; ++ i)        {            if(in[i] == 0)                ++ x;            if(out[i] == 0)                ++ y;        }        printf("%d\n%d\n", x, max(x, y));    }}
View Code

 

POJ 1236-Network of Schools (图论-有向图强联通tarjan)