洛谷 P2746 [USACO5.3]校园网 题解：强连通分量缩点应用
本题为经典的强连通分量（SCC）缩点问题，核心在于通过 Tarjan 算法将原图压缩为有向无环图（DAG），进而分析其结构特性。
第一问要求确定最少需要多少个初始学校才能使信息传播到所有学校。等价于在缩点后的 DAG 中，找出有多少个入度为 0 的连通块，因为这些是无法被其他块影响的起点。
第二问则要求添加最少的有向边，使得整个网络成为强连通图。根据图论结论，答案为 max(入度为 0 的连通块数, 出度为 0 的连通块数)。原因在于，要使整个图强连通，每个连通块必须至少有一条进入和一条离开的边，因此需补足缺失的"入口"或"出口"。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 10010
using namespace std;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') f = 0;
c = getchar();
}
while (isdigit(c)) {
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return f ? x : -x;
}
struct Edge {
int to, next;
} edges[MAXN];
int n, edgeCnt, nodeCnt, idx, stackTop, sccCount;
int head[MAXN], dfn[MAXN], low[MAXN], belong[MAXN], inDegree[MAXN], outDegree[MAXN];
bool instack[MAXN];
int sizeOfScc[MAXN];
inline void addEdge(int u, int v) {
edgeCnt++;
edges[edgeCnt].to = v;
edges[edgeCnt].next = head[u];
head[u] = edgeCnt;
}
void tarjan(int u) {
dfn[u] = low[u] = ++idx;
stack[++stackTop] = u;
instack[u] = true;
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
sccCount++;
int cur;
do {
cur = stack[stackTop--];
instack[cur] = false;
belong[cur] = sccCount;
sizeOfScc[sccCount]++;
} while (cur != u);
}
}
int main() {
memset(head, -1, sizeof(head));
n = read();
for (int i = 1; i <= n; i++) {
int target;
while ((target = read()) != 0) {
addEdge(i, target);
}
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i);
}
}
// 统计缩点后各强连通分量的入度与出度
for (int u = 1; u <= n; u++) {
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to;
if (belong[u] != belong[v]) {
outDegree[belong[u]] = 1;
inDegree[belong[v]] = 1;
}
}
}
// 第一问：入度为 0 的连通块数量
int zeroIn = 0;
for (int i = 1; i <= sccCount; i++) {
if (inDegree[i] == 0) zeroIn++;
}
// 第二问：取入度为 0 和出度为 0 的最大值
int zeroOut = 0;
for (int i = 1; i <= sccCount; i++) {
if (outDegree[i] == 0) zeroOut++;
}
if (sccCount == 1) {
printf("1\n0");
} else {
printf("%d\n%d", zeroIn, max(zeroIn, zeroOut));
}
return 0;
}
