POJ 1236 Network of Schools 题解《挑战程序设计竞赛》

POJ 1236 Network of Schools 

校园网：给定N所学校和网络，目标是分发软件其他学校都可收到，求①所需最少分发学校数；②若任选学校都能收到，最低新增边数。

4.3成为图论大师之路 

强连通分量分解

还是睡不着，再来一发吧。同一个强连通分量内的顶点合并为一个，在这个DAG上计算出度和入度。①其实是求入度为0的顶点数，②则是求0出度和0入度顶点数的较大者，因为要将这两类顶点连起来。

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
#define MAX_V 100 + 2

int V;                      // 顶点数
vector<int> G[MAX_V];       // 图的邻接表表示
vector<int> rG[MAX_V];      // 反向图
vector<int> vs;             // 后序遍历顺序的顶点列表
bool used[MAX_V];           // 访问标记
int cmp[MAX_V];             // 所属强连通分量的拓补序
int in[MAX_V], out[MAX_V];  // 入度、出度

void add_edge(const int &from, const int &to)
{
    G[from].push_back(to);
    rG[to].push_back(from);
}

void dfs(const int &v)
{
    used[v] = true;
    for (int i = 0; i < G[v].size(); ++i)
    {
        if (!used[G[v][i]])
            dfs(G[v][i]);
    }
    vs.push_back(v);
}

void rdfs(const int &v, const int &k)
{
    used[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); ++i)
    {
        if (!used[rG[v][i]])
            rdfs(rG[v][i], k);
    }
}

int scc()
{
    memset(used, 0, sizeof(used));
    vs.clear();
    for (int v = 0; v < V; ++v)
    {
        if (!used[v])
            dfs(v);
    }
    memset(used, 0, sizeof(used));
    int k = 0;
    for (int i = vs.size() - 1; i >= 0; --i)
    {
        if (!used[vs[i]])
            rdfs(vs[i], k++);
    }

    return k;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d", &V);
    for (int u = 0; u < V; ++u)
    {
        int v;
        while (scanf("%d", &v) && v)
        {
            add_edge(u, --v);
        }
    }

    int n = scc();
    if (n == 1)
    {
        puts("1\n0");       // 特殊情况
        return 0;
    }
    for (int u = 0; u < V; ++u)
    {
        for (int i = 0; i < G[u].size(); ++i)
        {
            int v = G[u][i];
            if (cmp[u] != cmp[v])               // 强连通分量算一个点
                ++out[cmp[u]], ++in[cmp[v]];
        }
    }

    int zero_in = 0, zero_out = 0;
    for (int i = 0; i < n; ++i)
    {
        if (in[i] == 0)
            ++zero_in;
        if (out[i] == 0)
            ++zero_out;
    }
    printf("%d\n", zero_in);
    printf("%d\n", max(zero_in, zero_out));    // 入度为0的点和出度为0的点建立连接
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1236 Network of Schools 题解《挑战程序设计竞赛》