寒鸽儿のBlog

考虑缩点。

对缩点后的图：
会变成外向树/内向树森林,或者DAG。
对于入度为0的点需要放一个文件。
将入度为0和出度为0的点连边为最优的构建强连通图的策略。则第二个子问题的答案为入度为0与出度为0的点数目的最大值。
注意特判缩点后成为一个点的情况。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 123, M = N*N;
int head[N], ver[M], nex[M], my[M], tot;
inline void addedge(int u, int v) {
	ver[tot] = v; nex[tot] = head[u]; my[tot] = u; head[u] = tot++;
}

int dfn[N], low[N], cl[N], sta[N], num[N], ind[N], outd[N], col = 1, dfs_clock = 1, top = 0;
void dfs(int cur) {
	dfn[cur] = low[cur] = dfs_clock++;
	sta[top++] = cur;
	for(int i = head[cur]; ~i; i = nex[i]) {
		if(!dfn[ver[i]]) {
			dfs(ver[i]);
			low[cur] = min(low[cur], low[ver[i]]); 
		} else if(!cl[ver[i]]) {
			low[cur] = min(low[cur], dfn[ver[i]]);
		}
	}
	if(dfn[cur] == low[cur]) {
		--top;
		while(sta[top] != cur) {
			++num[col];
			cl[sta[top]] = col;
			--top;
		}
		cl[cur] = col;
		++num[col];
		++col;
	}
}

int main() {
	memset(head, -1, sizeof(head));
	int n, tmp;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &tmp);
		while(tmp) {
			addedge(i, tmp);
			scanf("%d", &tmp);
		}
	}
	for(int i = 1; i <= n; ++i) if(!dfn[i]) dfs(i);
	for(int i = 0; i < tot; ++i) {
		if(cl[my[i]] != cl[ver[i]]) {
			++ind[cl[ver[i]]]; ++outd[cl[my[i]]];
		}
	}
	if(col == 2) {
		printf("1\n0\n");
		return 0;
	}
	int ans1 = 0, ans2 = 0;
	for(int i = 1; i < col; ++i) {
		if(!ind[i]) ++ans1;
		if(!outd[i]) ++ans2;
	}
	ans2 = max(ans1, ans2);  
	printf("%d\n%d\n", ans1, ans2);
	return 0;
}