poj 1236 Network of Schools 缩点

缘起

日常浪费生命 poj 1236 Network of Schools

分析

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
N(2<=N<=100)各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输，
问题1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。
问题2，至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的
学校最终都能得到软件。

【输入】
第一行是N， 然后是N行， 第i行的数字是从学校i出发可到达的学习列表, 以0结束.

【输出】
任务1和任务2的答案

【样例输入】
5
2 4 3 0
4 5 0
0
0
1 0

【样例输出】
1
2

【限制】
1s

tarjan缩点之后，形成DAG. 然后问题1的答案是 入度为0的点的个数. 问题2的答案（玄学的）是max{出度为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
113
114
115
116
117
118
119
120
121
122
123
124
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,m, head[105],head1[105], cnt,cnt1, sccnum,t, low[105], timestamp[105], belong[105], indeg[105],outdeg[105];
vector<int> scc[105];
stack<int> s;
bool ins[105];

struct Arc
{
	int from, to, nxt;
}g[10005],g1[10005];

void addArc(int a, int b)
{
	g[cnt].from = a, g[cnt].to = b, g[cnt].nxt = head[a];
	head[a] = cnt++;
}

void dfs(int i)
{
	timestamp[i] = low[i] = ++t;
	s.push(i), ins[i] = true;
	for (int h = head[i],to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (!timestamp[to])
		{
			dfs(to);
			low[i] = min(low[i], low[to]);
		}
		else if (ins[to])
		{
			low[i] = min(low[i], low[to]);
		}
	}
	if (timestamp[i] ==low[i])
	{
		sccnum++;
		int j;
		do 
		{
			j = s.top(),s.pop(), ins[j] = false;
			scc[sccnum].push_back(j), belong[j] = sccnum;
		} while (j!=i);
	}
}

void tarjan()
{
	for (int i = 1; i<=n; i++)
	{
		if (!timestamp[i])
		{
			dfs(i);
		}
	}
}

void addArc1(int from, int to)
{
	g1[cnt1].from = from, g1[cnt1].to = to, g1[cnt1].nxt = head1[from];
	head1[from] = cnt1++;
}

void rebuild() // 缩点重构DAG
{
	for (int i = 0, from, to; i<cnt; i++)
	{
		from = belong[g[i].from], to = belong[g[i].to]; // 原弧g[i]两端点所属的scc
		if (from!=to)
		{
			addArc1(from, to);
			indeg[to]++;
			outdeg[from]++;
		}
	}
}

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	memset(head, -1, sizeof(head));
	memset(head1, -1, sizeof(head));
	for(int i = 1,a; i<=n; i++)
	{
		while(scanf("%d", &a),a)
		{
			addArc(i,a);
		}
	}
	tarjan();
	if (sccnum==1) // wa到吐~ 如果只有一个scc的话~ 要特别对待
	{
		puts("1\n0");
		return 0;
	}
	rebuild();
	int ans1 = 0, ans2 = 0;
	for (int i = 1; i<=sccnum;i++)
	{
		if (!indeg[i])
		{
			ans1++;
		}
		if (!outdeg[i])
		{
			ans2++;
		}
	}
	printf("%d\n%d\n", ans1, max(ans1, ans2));
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 160kB
Length 1956
Lang C++
Submitted 2019-09-08 21:36:53
Shared
RemoteRunId 20844368