-图论-强连通分量- [洛谷 P2746][USACO5.3]校园网Network of Schools

题目描述

一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 B 在 A 学校的分发列表中， A 也不一定在 B 学校的列表中。

你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。

输入格式

输入文件的第一行包括一个整数 N：网络中的学校数目（2 <= N <= 100）。学校用前 N 个正整数标识。

接下来 N 行中每行都表示一个接收学校列表（分发列表）。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。

输出格式

你的程序应该在输出文件中输出两行。

第一行应该包括一个正整数：子任务 A 的解。

第二行应该包括子任务 B 的解。

输入样例

5
2 4 3 0
4 5 0
0
0
1 0

输出样例

1
2

Solution

先求一下强连通分量，然后再缩点，最后统计一下出度入度就行了。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100010
namespace STman {
    template <typename Tp>
    inline void read(Tp &x) {
        #define C getchar()
        Tp f = 1;x = 0;
        char k = C;
        while (k < '0' || k > '9') {if (k == '-') f = -1;k = C;}
        while (k >= '0' && k <= '9') {x = x * 10 + k - '0';k = C;}
        x = x * f;
        #undef C
    }
    template <typename Tp>
    inline void write(Tp x) {
        if (x < 0) putchar('-') , x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename Tp>
    inline Tp max(Tp a , Tp b) {
        if (a > b) return a;
        else return b;
    }
    template <typename Tp>
    inline Tp min(Tp a , Tp b) {
        if (a < b) return a;
        else return b;
    }
    template <typename Tp>
    inline void swap(Tp &a , Tp &b) {
        Tp t = a;
        a = b;
        b = a;
    }
    template <typename Tp>
    inline Tp abs(Tp &a) {
        if (a < 0) return -a;
        else return a;
    }
    inline void sp() {
        putchar(32);
    }
    inline void et() {
        putchar(10);
    }
}
using namespace STman;
struct Edge {
    int v , nx;
}e[MAXN * 4];
int dfn[MAXN] , tot , m , ecnt , st[MAXN] , out[MAXN] , smen;
int hd , in[MAXN] , low[MAXN] , en[MAXN] , head[MAXN] , tim , smout , n;
bool vis[MAXN];
void add(int f , int t) {
    e[++ecnt] = (Edge) {t , head[f]};
    head[f] = ecnt;
}
void tarjan(int u) {
    dfn[u] = low[u] = ++tim;
    st[++hd] = u;
    vis[u] = 1;
    for (int i = head[u] ; i ; i = e[i].nx) {
        int v = e[i].v;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u] , low[v]);
        }
        else if (vis[v]) {
            low[u] = min(dfn[v] , low[u]);
        }
    }
    if (low[u] == dfn[u]) {
        tot++;
        int v;
        do {
            v = st[hd--];
            vis[v] = 0;
            in[v] = tot;
        } while(v != u);
    }
}
int main() {
    read(n);
    for (int i = 1 ; i <= n ; i++) {
        read(m);
        while (m != 0) {
            add(i , m);
            read(m);
        }
    }
    for (int i = 1 ; i <= n ; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    for (int i = n ; i >= 1 ; i--) {
        for (int j = head[i] ; j ; j = e[j].nx) {
            int to = e[j].v;
            if (in[to] != in[i]) {
                out[in[i]] = 1;
                en[in[to]] = 1;
            }
        }
    }
    for (int i = 1 ; i <= tot ; i++) {
        smen += en[i] == 1 ? 0 : 1;
        smout += out[i] == 1 ? 0 : 1;
    }
    if (tot == 1) {
        printf("1\n0");
        return 0;
    }
    printf("%d\n%d" , smen , max(smen , smout));
}