NOIP2015 Day1 T2(DFS)

首先就能想到建一个有向图,然后我们可以发现一个人能从别人那里听到自己的生日,当且仅当有向图中存在环,我们在输入时记录每个点的入度,如果一个点入度为0,则直接删除,如果和它相连的点在这个点删掉以后入度也为0,也要删除,因为这些点都不能形成环,之后用DFS求环,不断地更新最小环的大小即可。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
const int MAXN = 200000 + 5, INF = 1000000000;
int n, in[MAXN], vi[MAXN], ti[MAXN], ans;
void dfs1(int u) {
vi[u] = 1;//剪枝:无用点删除
in[ti[u]]--;
if (in[ti[u]]==0&&!vi[ti[u]]) dfs1(ti[u]);
}
void dfs2(int u, int step, int start) {
vi[u] = 1;//剪枝:经过了不再经过
if (u==start&&step!=0) ans = min(ans, step); else {
if (!vi[ti[u]]||ti[u]==start) {
dfs2(ti[u], step+1, start);
}
}
}
void clean() {
ms(in, 0), ms(vi, false);
ans = INF;
}
void init() {
clean();
for (int i=1;i<=n;i++) {
scanf("%d", &ti[i]);
in[ti[i]]++;
}
}
void solve() {
for (int i=1;i<=n;i++) if (!vi[i]&&in[i]==0) dfs1(i);
for (int i=1;i<=n;i++) if (!vi[i]) dfs2(i, 0, i);
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d", &n)==1) init(), solve();
return 0;
}
------ 本文结束 ------