蓝桥杯--小朋友崇拜圈（有向图求最大环）_求有向图最大环

题目描述

班里N个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。
在一个游戏中，需要小朋友坐一个圈，
每个小朋友都有自己最崇拜的小朋友在他的右手边。
求满足条件的圈最大多少人？

小朋友编号为1,2,3,…N
输入第一行，一个整数N（3<N<100000）
接下来一行N个整数，由空格分开。

要求输出一个整数，表示满足条件的最大圈的人数。

测试样例

• 输入：
  9
  3 4 2 5 3 8 4 6 9

• 则程序应该输出：
  4

• 输入：
  30
  22 28 16 6 27 21 30 1 29 10 9 14 24 11 7 2 8 5 26 4 12 3 25 18 20 19 23 17 13 15

• 程序应该输出：
  16

---

解题思路

每个小朋友都有一个最崇拜的人，然后求这个多个崇拜圈的最大人数。有向图找最大环，用拓扑排序预处理一下把入度为0的人check掉，这些都是不能在圈中的，剩下的必然是存在于某个圈中。dfs求每个圈的人数更新最大值。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <queue>

using namespace std;
const int maxn = (int)1e5;

int v[maxn],cnt[maxn],N;
int res;
bool vis[maxn];
queue<int> Q;

void TopSort () {
	while (!Q.empty()) {
		Q.pop();
	}
	for (int i = 1; i <= N; i++) {
		if (cnt[i] == 0) {
			Q.push(i);
		}
	}
	int now;
	while (!Q.empty()) {
		now = Q.front();
		Q.pop();
		vis[now] = true;
		cnt[v[now]]--;
		if (cnt[v[now]] == 0) {
			Q.push(v[now]);
		}
	}
}

void DFS (int idx, int cnt) {
	if (!vis[idx]) {
		vis[idx] = true;
		DFS(v[idx], cnt+1);
	}else {
		res = max(res, cnt);
	}
}

int main() {
	cin >> N;
	memset(cnt, 0, sizeof(cnt));
	memset(vis, false, sizeof(vis));
	for (int i = 1; i <= N; i++) {
		cin >> v[i];
		cnt[v[i]]++; //入度++
	}
	TopSort(); //把不是环的check
	res = 0;
	for (int i = 1; i <= N; i++) {
		if (!vis[i]) {
			DFS(i, 0);
		}
	}
	cout << res << endl;
	return 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