哪位大神提示下这道题目怎么做？并查集的应用

cuibaowenown2

题目描述

Bo has been in Changsha for four years. However he spends most of his time staying his small dormitory. One day he decides to get out of the dormitory and see the beautiful city. So he asks to Xi to know whether he can get to another bus station from a bus station. Xi is not a good man   because he doesn’t tell Bo directly. He tells to Bo about some buses’ routes. Now Bo turns to you and he hopes you to tell him whether he can get to another bus station from a bus station directly according to the Xi’s information.

输入

The first line of the input contains a single integer T (0<T<30) which is the number of test cases. For each test case, the first contains two different numbers representing the starting station and the ending station that Bo asks. The second line is the number n (0<n<=50) of buses’ routes which Xi tells. For each of the following n lines, the first number m (2<=m<= 100) which stands for the number of bus station in the bus’ route. The remaining m numbers represents the m bus station. All of the bus stations are represented by a number, which is between 0 and 100.So you can think that there are only 100 bus stations in Changsha.

输出

For each test case, output the “Yes” if Bo can get to the ending station from the starting station by taking some of buses which Xi tells. Otherwise output “No”. One line per each case. Quotes should not be included.

样例输入

3
0 3
3
3 1 2 3
3 4 5 6
3 1 5 6
0 4
2
3 0 2 3
2 2 4
3 2
1
4 2 1 0 3
样例输出
No
Yes
Yes

提示

来源

中南大学第五届大学生程序设计竞赛-热身赛

我的代码是：

1. #include <stdio.h>
   
2. 
   
3. int father[101];
   
4. int rank[101];
   
5. 
   
6. void Init()
   
7. {
   
8.         for (int i=0;i<=100;i++)
   
9.         {
   
10.                 father[i]=i;
    
11.                 rank[i]=0;
    
12.         }
    
13. }
    
14. 
    
15. int Find_Set(int index)
    
16. {
    
17.         int &x=father[index];
    
18.         return x == index ? index : x=Find_Set(x);
    
19. }
    
20. 
    
21. int Union(int x,int y)
    
22. {
    
23.         x = Find_Set(x);
    
24.         y = Find_Set(y);
    
25. 
    
26.         if (x == y)        return x;
    
27. 
    
28.         if (rank[x]<rank[y])
    
29.         {
    
30.                 father[x]=y;
    
31.                 return y;
    
32.         }
    
33.         else
    
34.         {
    
35.                 if (rank[x]==rank[y])
    
36.                 {
    
37.                         rank[x]++;
    
38.                 }
    
39.                 father[y]=x;
    
40.                 return x;
    
41.         }
    
42. }
    
43. 
    
44. int main()
    
45. {
    
46.         int T;
    
47.         scanf("%d",&T);
    
48.         while (T--)
    
49.         {
    
50.                 Init();
    
51. 
    
52.                 int src,des;
    
53.                 scanf("%d %d",&src,&des);
    
54. 
    
55.                 int n;
    
56.                 scanf("%d",&n);
    
57. 
    
58.                 while (n--)
    
59.                 {
    
60.                         int first;
    
61.                         scanf("%d",&first);
    
62.                         while (getchar()!='\n')
    
63.                         {
    
64.                                 int last;
    
65.                                 scanf("%d",&last);
    
66.                                 if (first != last)
    
67.                                         first=Union(first,last);
    
68.                         }
    
69.                 }
    
70.                 if (Find_Set(src) == Find_Set(des))
    
71.                         printf("Yes\n");
    
72.                 else
    
73.                         printf("No\n");
    
74.         }
    
75.         return 0;
    
76. }

复制代码

用的是并查集，但是会超时。用了按秩合并和路径压缩，但还是超时了

HHR

看完应该能懂

cuibaowenown2

HHR 发表于 2014-5-1 09:57

                               
登录/注册后可看大图

看完应该能懂

东西我看过了。。。都是我已经会了的。我用上了并查集以及按秩合并、路径压缩。。已经比你发的东西还要高效了。。不信你看我代码。。但是还是超时了。纳闷儿了。。

rockerz

http://courses.cs.washington.edu/courses/cse326/09wi/lectures/19-disjoint-union-find-part-2.pdf
看一下他的union-by-size。 应该有用。

cuibaowenown2

我知道为毛了。。题目读错了。。。。。。。。:huffy::huffy::huffy::huffy::huffy::huffy::huffy::huffy:

聆听丨灬六月

我也刚学数据结构，不会，过来打个酱油，嘿嘿