P2661 信息传递 – Xhesica's blog

链接：P2661

--------------------------------

这道题有加权并查集的影子

--------------------------------

思路还是好想的，根据特性，可以得到如果得到了一条从A到B的边后形成了环，则一定有他们的公共祖先是b。这样就明白了，然后把这个环拆成三部分，这一条边以及B到A、A到B（不加上这条边），他们的和就是长度

-----------------------------

一定不能把A，B连起来

-------------------------------

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 int dis[200005];
 6 int fa[200005];
 7 //int x,y;
 8 int n;
 9 int minn=0x7f7f7f7f;
10 int find(int x){
11     if(fa[x]!=x){
12         int last = fa[x];
13         fa[x]=find(fa[x]);
14         dis[x]+=dis[last];
15     }
16     return fa[x];
17 }
18 
19 void deal(int a,int b){
20 //        cout<<a<<" "<<b<<endl;
21     int x=find(a);
22     int y=find(b);
23     if(x!=y){
24         fa[x]=y;
25         dis[a]=dis[b]+1;
26     }
27     else
28     minn=min(minn,dis[a]+dis[b]+1);
29 }
30 
31 int main(){
32     cin>>n;
33     int t;
34     for(int i=1;i<=n;++i)
35     fa[i]=i;
36     for(int i=1;i<=n;++i){
37         cin>>t;
38         deal(i,t);
39     }
40     cout<<minn;
41     return 0;
42 }

发送评论编辑评论

发送评论 编辑评论

发送评论编辑评论