2010辽宁省赛You are my brother

**题目描述
Little A gets to know a new friend, Little B, recently. One day, they realize that they are family 500 years ago. Now, Little A wants to know whether Little B is his elder, younger or brother.
输入
There are multiple test cases.
For each test case, the first line has a single integer, n (n<=1000). The next n lines have two integers a and b (1<=a,b<=2000) each, indicating b is the father of a. One person has exactly one father, of course. Little A is numbered 1 and Little B is numbered 2.
Proceed to the end of file.
输出
For each test case, if Little B is Little A’s younger, print “You are my younger”. Otherwise, if Little B is Little A’s elder, print “You are my elder”. Otherwise, print “You are my brother”. The output for each test case occupied exactly one line.
样例输入
5
1 3
2 4
3 5
4 6
5 6
6
1 3
2 4
3 5
4 6
5 7
6 7
样例输出
You are my elder
You are my brother**

题意就是 输入n行,每行两个整数,表示前者是儿子,后者是父亲,第一行输入A的关系,第二行输入B的关系,最后他们的祖先必然相同,如果A的节点数大于B的,则说明You are my elder,相等时You are my brother,小于时You are my younger。

1:由于是单源路径,所以可以只用一个数组存储节点之间的关系。
2:数组初始化为自身是自身的父亲,下标为儿子,存储的元素为父亲。
3:在一个循环内,如果自身不是自身的父亲,既不是他们的共同祖先时,就继续往后查找,sum变量和count分别记录A和B的节点数,最后进行比较即可。
(为什么这。。。让我想起了并查集)

#include<stdio.h>
#include<string.h>
int f[2000];

int main()
{
    int sum,count;
    int i,n,a,b,k,l;
    while(scanf("%d",&n)!=EOF)
    {
        memset(f,0,sizeof(f));
        for( i = 1; i <= n; i ++)//步骤2
            f[i] = i;
        for( i =1; i <= n; i ++)
        {
            scanf("%d%d",&a,&b);
            f[a] = b;
        }
        k = 1;
        sum = 0;
        while(f[k] != k)//步骤3
        {
            sum ++;
            k = f[k];
        }
        l = 2;
        count = 0;
        while(f[l] != l)
        {
            count++;
            l = f[l];
        }
        if( sum < count)
            printf("You are my younger
");
        else if( sum == count)
            printf("You are my brother
");
        else
            printf("You are my elder
");
    }
    return 0;
}

错误点:
学校的OJ让我很心碎啊 明明数组开到了1100就满足题意,它却显示运行错误,我改到2000就AC了

后记:这道题明明不初始化置0也没毛病啊,然而,它直接显示时间超限,今天练习赛的一道Kruskal纯模板题,我手动quicksort就导致超限,学长说直接用C++模板库里的sort就行,现在太菜,还分不清这些排序的时间复杂度的区别

原文地址:https://www.cnblogs.com/hellocheng/p/7350167.html