一些学校连接到计算机网络。这些学校之间已经达成了协议：
每所学校都有一份分发软件的学校名单（“接收学校”）。
请注意，如果B在学校A的分发名单中，则A不一定出现在学校B的名单中
您需要编写一个计划，计算必须接收新软件副本的最少学校数量，
以便软件根据协议（子任务A）到达网络中的所有学校。作为进一步的任务，
我们希望确保通过将新软件的副本发送到任意学校，该软件将覆盖网络中的所有学校。
为了实现这一目标，我们可能需要扩大新成员的接收者名单。
计算必须做的扩展的最小数目，以便我们发送新软件的任何学校，
它将到达所有其他学校（Subtask B）。
一种扩展意味着将一名新成员引入一所学校的接收者名单。
这题强连通水题 ，模板题目，
第一问求出最少要几个点才能到任意点
其实就是一个强连通缩点后，求出有几个入度为0的点，
第二问求出要加上几条边把所点后的有向无环图变成一个强连通图
就是求 max(sumin, sumout)
1 #include <cstdio> 2 #include <cstring> 3 #include <string> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 ?8 const int maxn = 1e5 + 10; 9 int n, m, u, v, tot, top, cnt, flag;10 struct node {11 ????int v, next;12 } edge[maxn];13 int head[maxn], instack[maxn], s[maxn];14 int dfn[maxn], low[maxn], belong[maxn];15 void init() {16 ????tot = cnt = top = flag = 0;17 ????memset(s, 0, sizeof(s));18 ????memset(head, -1, sizeof(head));19 ????memset(dfn, 0, sizeof(dfn));20 ????memset(instack, 0, sizeof(instack));21 }22 void add(int u, int v) {23 ????edge[tot].v = v;24 ????edge[tot].next = head[u];25 ????head[u] = tot++;26 }27 void tarjin(int v) {28 ????dfn[v] = low[v] = ++flag;29 ????instack[v] = 1;30 ????s[top++] = v;31 ????for (int i = head[v] ; i != -1 ; i = edge[i].next) {32 ????????int j = edge[i].v;33 ????????if (!dfn[j]) {34 ????????????tarjin(j);35 ????????????low[v] = min(low[v], low[j]);36 ????????} else if (instack[j]) low[v] = min(low[v], dfn[j]);37 ????}38 ????if (dfn[v] == low[v]) {39 ????????cnt++;40 ????????int t;41 ????????do {42 ????????????t = s[--top];43 ????????????instack[t] = 0;44 ????????????belong[t] = cnt;45 ????????} while(t != v) ;46 ????}47 }48 void solve() {49 ????for (int i = 1 ; i <= n ; i++)50 ????????if (!dfn[i]) tarjin(i);51 }52 int in[maxn], out[maxn];53 int main() {54 ????while(scanf("%d", &n) != EOF) {55 ????????init();56 ????????memset(in, 0, sizeof(in));57 ????????memset(out, 0, sizeof(out)) ;58 ????????for (int i = 1 ; i <= n ; i++) {59 ????????????int v;60 ????????????scanf("%d", &v);61 ????????????while(v) {62 ????????????????add(i, v);63 ????????????????scanf("%d", &v);64 ????????????}65 ????????}66 ????????for (int i = 1 ?; i <= n ; i++)67 ????????????if (!dfn[i]) tarjin(i);68 ????????for (int i = 1 ; i <= n ; i++) {69 ????????????for (int j = head[i] ; ~j ; j = edge[j].next) {70 ????????????????if (belong[edge[j].v] != belong[i]) {71 ????????????????????in[belong[edge[j].v]]++;72 ????????????????????out[belong[i]]++;73 ????????????????}74 ????????????}75 ????????}76 ????????int sumin = 0, sumout = 0;77 ????????for (int i = 1 ; i <= cnt ; i++) {78 ????????????if (!in[i]) sumin++;79 ????????????if (!out[i])sumout++;80 ????????}81 ????????printf("%d\n", sumin);82 ????????if (cnt == 1) printf("0\n");83 ????????else printf("%d\n", max(sumin, sumout));84 ????}85 ????return 0;86 }poj~1236 Network of Schools 强连通入门题
原文地址：https://www.cnblogs.com/qldabiaoge/p/9073147.html