题目地址：洛谷：【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 的解。

输入输出样例

输入样例#1：

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

输出样例#1：

1
2

题解

由于强连通分量内部的点两两互达，不需要考虑内部的情况，直接缩点。对于子任务A，答案就是缩点后入度为0的点的数量，因为当所有入度为0的点都被分发了，入度大于0的点也会被分发，反过来说，如果只分发给入度大于0的点，入度为0的点永远不会被分发到。对于子任务B，考虑只需要从出度为0的点向入度为0的点连边即可，因此答案是出度为0的点的数量和入度为0的点的数量的较大值。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>
#include <stack>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 105;

int n, m;

std::vector<int> gra[MAXN];

int dfn[MAXN], low[MAXN], sno[MAXN], scc, clk;
std::stack<int> sta;
bool insta[MAXN];

inline void tarjan(int u) {
    dfn[u] = low[u] = ++clk;
    insta[u] = true; sta.push(u);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if(insta[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        scc++;
        int p;
        do {
            p = sta.top(); sta.pop(); insta[p] = false;
            sno[p] = scc;
        } while(p != u);
    }
}

int ind[MAXN], outd[MAXN];

int v;

int main() {
    n = readint();
    for(int u = 1; u <= n; u++) {
        for(;;) {
            v = readint(); if(!v) break;
            gra[u].push_back(v);
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++) {
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i];
            if(sno[u] != sno[v]) {
                outd[sno[u]]++;
                ind[sno[v]]++;
            }
        }
    }
    if(scc == 1) {
        puts("1\n0");
        return 0;
    }
    int out0 = 0, in0 = 0;
    for(int i = 1; i <= scc; i++) {
        if(!ind[i]) in0++;
        if(!outd[i]) out0++;
    }
    printf("%d\n%d", in0, std::max(out0, in0));
    return 0;
}