POJ原题链接

洛谷2746原题链接

洛谷2812(加强版)原题链接

显然在强连通分量里的所有学校都能通过网络得到软件，所以我们可以用\(tarjan\)求出强连通分量并缩点，统计缩点后每个点的入度和出度。

对于第一问，因为所有零入度的点无法通过网络得到软件，所以答案就是零入度的点的数量。

对于第二问，若有\(x\)个零入度的点，\(y\)个零出度的点，则答案就是\(\max\{x,y\}\)。注意当图被缩成一个点时，答案为\(0\)。

#include<cstdio>

using namespace std;

const int N = 110;//对于加强版，只需开大空间即可

const int M = 1e4 + 10;

int fi[N], di[M], ne[M], dfn[N], low[N], st[N], bl[N], ru[N], ch[N], l, ti, tp, SCC;

bool v[N];

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline void add(int x, int y)

{

	di[++l] = y;

	ne[l] = fi[x];

	fi[x] = l;

}

inline int minn(int x, int y)

{

	return x < y ? x : y;

}

inline int maxn(int x, int y)

{

	return x > y ? x : y;

}

void tarjan(int x)

{

	int i, y;

	dfn[x] = low[x] = ++ti;

	st[++tp] = x;

	v[x] = 1;

	for (i = fi[x]; i; i = ne[i])

	{

		y = di[i];

		if (!dfn[y])

		{

			tarjan(y);

			low[x] = minn(low[x], low[y]);

		}

		else

			if (v[y])

				low[x] = minn(low[x], dfn[y]);

	}

	if (!(dfn[x] ^ low[x]))

	{

		++SCC;

		do

		{

			y = st[tp--];

			v[y] = 0;

			bl[y] = SCC;

		} while (x ^ y);

	}

}

int main()

{

	int i, x, y, z, n, s_1 = 0, s_2 = 0;

	n = re();

	for (i = 1; i <= n; i++)

		for (x = re(); x; x = re())

			add(i, x);

	for (i = 1; i <= n; i++)

		if (!dfn[i])

			tarjan(i);

	for (z = 1; z <= n; z++)

		for (i = fi[z]; i; i = ne[i])

		{

			y = bl[di[i]];

			x = bl[z];

			if (x ^ y)

			{

				ru[y]++;

				ch[x]++;

			}

		}

	for (i = 1; i <= SCC; i++)

	{

		if (!ru[i])

			s_1++;

		if (!ch[i])

			s_2++;

	}

	printf("%d\n%d", s_1, SCC == 1 ? 0 : maxn(s_1, s_2));

	return 0;

}