【NOIP 2015 D1 T2】信息传递（图论--带权并查集/bfs）

题目：有n个同学（编号为1到n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为i的同学的信息传递对象是编号为Ti同学。游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？

解法：利用并查集将相连通的点连起来，可以使用带权并查集顺带计算每个点到父亲结点的距离，从而知道环的结点数。也可以bfs每个强联通分量找最小的环。

我去年比赛打的是bfs，这个代码是带权并查集。

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 using namespace std;

 6 #define N 200010

 7

 8 int fa[N],d[N];

 9

10 int mmin(int x,int y) {return x<y?x:y;}

11 int mabs(int x) {return x<0?-x:x;}

12 int ffind(int x)

13 {

14     if (fa[x]!=x)

15     {

16       int y=fa[x];

17       fa[x]=ffind(y);

18       d[x]+=d[y];

19     }

20     return fa[x];

21 }

22 int main()

23 {

24     int n,x,y;

25     scanf("%d",&n);

26     int mn=n;

27     for (int i=1;i<=n;i++) fa[i]=i,d[i]=0;//表示到祖先的距离

28     for (int i=1;i<=n;i++)

29     {

30       scanf("%d",&y);

31       x=i;

32       int fx=ffind(x),fy=ffind(y);

33       if (fx!=fy)

34       {

35         fa[x]=fy;//不可反，由于建树是有顺序的，想判环必须是编号大的点为父亲

36         d[x]=d[y]+1;

37       }

38       else mn=mmin(mn,d[y]+1);

39     }

40     //bfs() 或 带权并查集

41     printf("%d\n",mn);

42     return 0;

43 }

Code1

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<cmath>

 5 #include<iostream>

 6 #include<algorithm>

 7 #include<set>

 8 using namespace std;

 9

10 const int N=210000,INF=(int)1e9;

11 int n,fa[N],d[N];

12

13 int minn(int x,int y){return x<y ? x:y;}

14

15 int findfa(int x)

16 {

17     if(fa[x]!=x)

18     {

19         int xx=fa[x];

20         fa[x]=findfa(fa[x]);

21         d[x]=d[x]+d[xx];

22     }

23     return fa[x];

24 }

25

26 int main()

27 {

28     scanf("%d",&n);

29     int x,y,xx,yy,ans=INF;

30     for(int i=1;i<=n;i++) fa[i]=i,d[i]=0;

31     for(int i=1;i<=n;i++)

32     {

33         x=i;

34         scanf("%d",&y);

35         xx=findfa(x);yy=findfa(y);

36         if(xx==yy)

37         {

38             ans=minn(ans,d[x]+d[y]+1);

39         }

40         else

41         {

42             fa[xx]=x;

43             d[xx]=d[x];

44             fa[x]=y;

45             d[x]=1;

46         }

47     }

48     printf("%d\n",ans);

49     return 0;

50 }

Code2(by gyw)

巴特西

【NOIP 2015 D1 T2】信息传递（图论--带权并查集/bfs）

最新文章

热门文章