本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15630249.html

题目链接

我们先对于有向图缩点，变成一棵树。

然后我们对于每个树上且在原图中的分割点节点所对应原图中的连通块考虑。

假设这里没有割点，很明显，只需要放2个出口即可。

如果有一个割点，说明这个点是树上的叶子节点，需要放1个出口。

如果有两个或以上的割点，无论哪个割点被割，都可以往另一个方向逃，所以这个连通块不用放。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// Problem: P3225 [HNOI2012]矿场搭建
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3225
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define mo
#define M 510
#define N 1010
struct node
{
	int x, y, n; 
}d[M*2]; 
int n, m, i, j, k, T; 
int h[N], dep[N], c[N], w[N], f[N], zi[N];
int u, v, ansx, ansy, a, b; 

void cun(int x, int y)
{
	n=max(n, x); 
	d[++k].x=x; d[k].y=y; 
	d[k].n=h[x]; h[x]=k; 
}

void dfs(int x)
{
	for(int g=h[x]; g; g=d[g].n)
	{
		int y=d[g].y; 
		if(!dep[y])
		{
			dep[y]=dep[x]+1; 
			dfs(y); 
			if(dep[f[y]]>=dep[x]) ++zi[x]; 
			if(dep[f[y]]<dep[f[x]]) f[x]=f[y]; 
		}
		else if(dep[y]<dep[f[x]]) f[x]=y; 
	}
}

void foofill(int x)
{
	for(int g=h[x]; g; g=d[g].n)
	{
		int y=d[g].y; 
		if(c[y]<j)
		{
			c[y]=j; 
			if(w[y]) ++b; 
			else ++a, foofill(y); 
		}
	}
}

void init()
{
	n=m=i=j=k=u=v=ansx=ansy=a=b=0; 
	memset(h, 0, sizeof(h)); 
	memset(dep, 0, sizeof(dep)); 
	memset(c, 0, sizeof(c)); 
	memset(w, 0, sizeof(w)); 
	memset(f, 0, sizeof(f)); 
	memset(zi, 0, sizeof(zi)); 
}

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	while(1)
	{
		init(); 
		m=read(); 
		if(!m) return 0; 
		printf("Case %lld: ", ++T); 
		// printf("\n"); 
		for(i=1; i<=m; ++i)
		{
			u=read(); v=read(); 
			cun(u, v); cun(v, u); 
		}
		// printf("%lld ", n); 
		for(i=1; i<=n; ++i) f[i]=i; 
		for(i=1; i<=n; ++i)
			if(!dep[i])
				dep[i]=1, dfs(i); 
		// for(i=1; i<=n; ++i)
			// printf("%lld %lld %lld\n", i, f[i], zi[i]); 
		for(i=1; i<=n; ++i)
			if((dep[i]!=1&&zi[i])||(zi[i]>=2))
				w[i]=1; 
		// for(i=1; i<=n; ++i) printf("%lld ", w[i]); 
		// printf("-------------------\n"); 
		ansy=1; 
		for(i=1, j=0; i<=n; ++i)
			if(c[i]==0&&w[i]==0&&h[i])
			{
				c[i]=(++j); 
				b=0; a=1; 
				foofill(i); 
				if(b==0) 
				{
					if(a==1) ++ansx; 
					else ansx+=2, ansy*=(a*(a-1)/2); 
				}
				else if(b==1) ++ansx, ansy*=a; 
				// printf("%lld %lld %lld %lld\n", i, a, b, j); 
			}
		printf("%lld %lld\n", ansx, ansy); 
	}
	return 0;
}