我知道应该去学点新的东西。不过今天仍然做了一道缩点，名字叫校园网络
这道题的做法显而易见：缩点后，第一个任务是找出所有入度为0的点的个数，只有这些点是必须手动发送的。第二个任务则是求出max(出度为0的点的个数，入度为0的点的个数) 显然如果一张图强联通那么没有点入度为0，也没有点出度为0，所以连边就是要把每一个出度/入度为0的连到那个起点上面，或者从起点连过来。
代码：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
using namespace std;
int n;
struct Edge
{
int v,next;
}e[1005],e1[1005];
int cnt = 0,front[1005],dfn[1005],low[1005],co[1005];
int rudu[1005],chud[1005],stk[1005],vis[1005],num[1005];
bool instk[1005];
int tp = 0,t = 0,tot = 0;
int cnt1 = 0,front1[105];
void AddEdge(int u,int v)
{
e[++cnt].v = v;
e[cnt].next = front[u];
front[u] = cnt;
}
void AddEdge1(int u,int v)
{
rudu[v]++;
chud[u]++;
e1[++cnt1].v = v;
e1[cnt1].next = front1[u];
front1[u] = cnt1;
}
void tarjan(int now)
{
instk[now] = true;
stk[++tp] = now;
dfn[now] = low[now] = ++t;
for (int i = front[now]; i; i = e[i].next)
{
int xx = e[i].v;
if (!dfn[xx])
{
tarjan(xx);
low[now] = min(low[now],low[xx]);
}
else if (instk[xx])
{
low[now] = min(low[now],dfn[xx]);
}
}
if (dfn[now] == low[now])
{
tot++;
while (stk[tp + 1] != now)
{
int xx = stk[tp];
tp--;
instk[xx] = false;
co[xx] = tot;
num[tot] = xx;
}
}
}
int main()
{
scanf("%d",&n);
for (int i = 1; i <= n; i++)
{
int t;
while (scanf("%d",&t))
{
if (t == 0) break;
else
{
AddEdge(i,t);
}
}
}
for (int i = 1; i <= n; i++)
{
if (!dfn[i]) tarjan(i);
}
for (int k = 1; k <= n; k++)
{
for (int i = front[k]; i; i = e[i].next)
{
int xx = e[i].v;
if(co[k] != co[xx])
{
AddEdge1(co[k],co[xx]);
//cout<<num[k]<<"-->"<<num[]
}
}
}
int res1 = 0, res2 = 0;
for (int i = 1; i <= tot; i++)
{
if (rudu[i] == 0 && !vis[i])
{
res1++;
for (int j = front1[i]; j; j = e[j].next)
{
vis[j] = true;
}
// cout<<num[i]<<endl;
}
if (chud[i] == 0) res2++;
}
//cout<<"s: "<<res1<<" "<<res2<<endl;
if (tot == 1) res2 = 0;
else
{
res2 = max(res1,res2);
}
printf("%d\n%d",res1,res2);
return 0;
}