acwing 517. 信息传递
标签：ast 方式 push cti lin 表示 别人 告诉 mil
地址 https://www.acwing.com/problem/content/description/519/
有 n 个同学（编号为 1 到 n）正在玩一个信息传递的游戏。
在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 TiTi 的同学。
游戏开始时，每人都只知道自己的生日。
之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。
当有人从别人口中得知自己的生日时，游戏结束。
请问该游戏一共可以进行几轮？
输入格式
输入共 2 行。
第 1 行包含 1 个正整数 n ，表示 n 个人。
第 2 行包含 n 个用空格隔开的正整数T1,T2,…,Tn，其中第 i 个整数 Ti 表示编号为 i 的同学的信息传递对象是编号为 Ti 的同学，Ti ≤n 且 Ti ≠i。
数据保证游戏一定会结束。
输出格式
输出共 1 行，包含 1 个整数，表示游戏一共可以进行多少轮。
数据范围
n≤200000
输入样例：
5
2 4 2 3 1
输出样例：
3
解法
每个人看做点 通讯的途径看做边的话 这里就是求最短的环。
应该可以使用搜索的方式获取最短的环
我们这里没使用这种方式 而是使用tarjan求环
1 #include 2 #include 3 #include 4 #include
5
6 using namespace std;
7
8 const int maxn = 2e5 + 7;
9 vectorint> E[maxn];
10 int vis[maxn];
11 int dfn[maxn], low[maxn], tot, n, ans = maxn;
12 stackint> s;
13
14 void tarjan(int x)
15 {
16 low[x] = dfn[x] = ++ tot;
17 s.push(x); vis[x] = 1;
18
19 for (int i = 0; i ) {
20 int v = E[x][i];
21 if (!dfn[v]) {
22 tarjan(v);
23 low[x] = min(low[x], low[v]);
24 }
25 else if (vis[v]) {
26 low[x] = min(low[x], dfn[v]);
27 }
28 }
29
30 if (low[x] == dfn[x]) {
31 int cnt = 0;
32 while (1) {
33 int now = s.top();
34 s.pop();
35 vis[x] = 0;
36 cnt++;
37 if (now == x) break;
38 }
39 if (cnt > 1) ans = min(ans, cnt);
40 }
41
42 }
43
44 int main()
45 {
46 scanf("%d",&n );
47 for (int i = 1; i ) {
48 int x;
49 scanf("%d", &x);
50 E[i].push_back(x);
51 }
52
53 for (int i = 1; i ) {
54 if (!dfn[i])
55 tarjan(i);
56 }
57
58 cout endl;
59
60 return 0;
61 }
tarjan
还可以考虑使用并查集的办法 找到最小的并查集即可
1 #include 2
3 using namespace std;
4
5
6 const int N = 200000+1000;
7 int fa[N],n,m,i,j,k,cnt,ans = 1e9;
8
9 int find(int x)
10 {
11 cnt++;
12 return fa[x]==x?x:find(fa[x]);
13 }
14
15
16 int main(){
17 cin >> n;
18 for(int i = 1;i )
19 fa[i] = i;
20 for(int i = 1;i ){
21 int x;
22 cin >> x;
23 cnt = 0;
24 if(find(x) == i)
25 ans = min(ans,cnt);
26 else
27 fa[i] = x;
28 }
29
30 cout ans;
31 return 0;
32 }
View Code
acwing 517. 信息传递
标签：ast 方式 push cti lin 表示 别人 告诉 mil
原文地址：https://www.cnblogs.com/itdef/p/11870075.html
评论