POJ 1236 学校传数据强连通+缩点+DAG

网络中有一些学校，每个学校可以分发软件给其他学校。可以向哪个分发取决于他们各自维护的一个清单。

两个问题

1：至少要copy多少份新软件给那些学校，才能使得每个学校都能得到。

2:要在所有的学校的清单里面至少一共增加几项才能使得把软件给任意一个学校，所有的学校都能收得到。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-10;
const int  inf =0x7f7f7f7f;
const double pi=acos(-1);
const int maxn=100;

vector<int> G[maxn+10];
int n,m,degin[maxn+10],degout[maxn+10],pre[maxn+10],dfs_clock,scc_cnt,sccno[maxn+10],lowlink[maxn+10];
stack<int> S;

void tarjan(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])
            {
                tarjan(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++;
        while(1)
        {
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            if(x==u) break;
        }
    }
}

void find_scc()
{
    MM(pre,0);
    MM(sccno,0);
    scc_cnt=dfs_clock=0;
    for(int i=1;i<=n;i++)
      if(!pre[i])
        tarjan(i);
}

int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
            G[i].clear();


        for(int i=1;i<=n;i++)
            {
              int u;
              while(~scanf("%d",&u)&&u)
                 G[i].push_back(u);
            }

        MM(degin,0);
        MM(degout,0);
        find_scc();

        int in0=0,out0=0;
        for(int u=1;u<=n;u++)
            for(int j=0;j<G[u].size();j++)
             {
               int v=G[u][j];
               if(sccno[u]==sccno[v]) continue;
               degin[sccno[v]]++;
               degout[sccno[u]]++;
             }

        for(int i=1;i<=scc_cnt;i++)
            {
                if(!degin[i]) in0++;
                if(!degout[i]) out0++;
            }

        if(scc_cnt==1) printf("1
0
");
        else printf("%d
%d
",in0,max(in0,out0));
    }
    return 0;
}

分析：很好的一道题

1：第一问，其实只要求出整个图中缩点后（强连通）入度数为0的点个数就好，因为缩成DAG后只要一个点

有入度，那么我们肯定可以通过他的入度的那个点给他传信息；

2.其实就是在问，给缩点之后的DAG添加多少条边可以使得DAG变成强连通，对于一个DAG只要他入度为0的点与出度为0的点均不存在，那么就可以缩成强连通，每添加一条边，可同时消灭一个出度为0的点与入度为0的点，所以取这两种点的最大值就好；

3,最后特判一下原图本就是强连通的情况，因为这时degin[1]与degout[1]均会++

证明：反证法

如果一个DAG里面，每个点的出度都不为0，那么从任意一个点v1出发，都可以找到v2满足<v1,v2>属于G

这样可以一直生成一个序列v1, v2, v3...因为图是有限的，这个序列一定会有环，所以这个图不是DAG

POJ 1236 学校传数据 强连通+缩点+DAG

POJ 1236 学校传数据强连通+缩点+DAG