1921. 重新排列奶牛
摘要
Title: 1921. 重新排列奶牛
Tag: 并查集、找环
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1921. 重新排列奶牛
-
题意
见原题
-
思路
如这个例子
a = [5, 1, 4, 2, 3]
idx = [2, 4, 5, 3, 1] (就是a中每个数的下标)
b = [2, 5, 3, 1, 4]
发现可以进行连边找环，有向图且环与环之间不相交
那么对于 有向环图中 环 等价于 连通块
-
代码
- 循环模拟找环
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'''
Author: NEFU AB-IN
Date: 2022-05-15 22:07:30
FilePath: \ACM\Acwing\1921.py
LastEditTime: 2022-05-15 22:54:45
'''
n = int(input())
a = [0]
b = [0]
idx = [0] * (n + 1)
for i in range(1, n + 1):
a.append(int(input()))
idx[a[i]] = i
for i in range(1, n + 1):
b.append(int(input()))
ans = -1
cnt = 0
vis = [0] * (n + 1)
for i in range(1, n + 1):
id = idx[i]
tmp = 0
while True:
if vis[id]:
break
vis[id] = 1
t = b[id]
id = idx[t]
tmp += 1
if id == idx[i] and tmp > 1:
cnt += 1
ans = max(ans, tmp)
break
print(cnt, ans)
- 并查集找环
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'''
Author: NEFU AB-IN
Date: 2022-05-16 08:23:19
FilePath: \ACM\Acwing\1921.1.py
LastEditTime: 2022-05-16 08:55:15
'''
N = 110
fa = [i for i in range(N)]
s = [1] * N
a = [0]
b = [0]
idx = [0] * N
def find(x):
if fa[x] != x:
fa[x] = find(fa[x])
return fa[x]
n = int(input())
for i in range(1, n + 1):
a.append(int(input()))
idx[a[i]] = i
for i in range(1, n + 1):
b.append(int(input()))
for i in range(1, n + 1):
x = idx[i]
y = idx[b[x]]
if find(x) != find(y):
s[find(x)] += s[find(y)]
fa[find(y)] = find(x)
cnt, ans = 0, -1
for i in range(1, n + 1):
if fa[i] == i and s[i] > 1:
cnt += 1
ans = max(ans, s[i])
print(cnt, ans)
