cuibaowenown2 发表于 2014-5-1 09:51:19

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

本帖最后由 cuibaowenown2 于 2014-5-1 11:41 编辑

题目描述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

提示

来源中南大学第五届大学生程序设计竞赛-热身赛
我的代码是：#include <stdio.h>

int father;
int rank;

void Init()
{
        for (int i=0;i<=100;i++)
        {
                father=i;
                rank=0;
        }
}

int Find_Set(int index)
{
        int &x=father;
        return x == index ? index : x=Find_Set(x);
}

int Union(int x,int y)
{
        x = Find_Set(x);
        y = Find_Set(y);

        if (x == y)        return x;

        if (rank<rank)
        {
                father=y;
                return y;
        }
        else
        {
                if (rank==rank)
                {
                        rank++;
                }
                father=x;
                return x;
        }
}

int main()
{
        int T;
        scanf("%d",&T);
        while (T--)
        {
                Init();

                int src,des;
                scanf("%d %d",&src,&des);

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

                while (n--)
                {
                        int first;
                        scanf("%d",&first);
                        while (getchar()!='\n')
                        {
                                int last;
                                scanf("%d",&last);
                                if (first != last)
                                        first=Union(first,last);
                        }
                }
                if (Find_Set(src) == Find_Set(des))
                        printf("Yes\n");
                else
                        printf("No\n");
        }
        return 0;
}
用的是并查集，但是会超时。用了按秩合并和路径压缩，但还是超时了





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

看完应该能懂

cuibaowenown2 发表于 2014-5-1 10:05:42

HHR 发表于 2014-5-1 09:57 static/image/common/back.gif
看完应该能懂

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

rockerz 发表于 2014-5-1 11:20:40

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

cuibaowenown2 发表于 2014-5-1 12:13:43

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

聆听丨灬六月 发表于 2014-5-15 10:52:07

我也刚学数据结构，不会，过来打个酱油，嘿嘿
页: [1]
查看完整版本: 哪位大神提示下这道题目怎么做？并查集的应用