首页 > ACM题库 > HDU-杭电 > HDU 3342-Legal or Not-拓扑排序-[解题报告]HOJ
2014
03-16

HDU 3342-Legal or Not-拓扑排序-[解题报告]HOJ

Legal or Not

问题描述 :

ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many "holy cows" like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When someone has questions, many warm-hearted cows like Lost will come to help. Then the one being helped will call Lost "master", and Lost will have a nice "prentice". By and by, there are many pairs of "master and prentice". But then problem occurs: there are too many masters and too many prentices, how can we know whether it is legal or not?

We all know a master can have many prentices and a prentice may have a lot of masters too, it’s legal. Nevertheless,some cows are not so honest, they hold illegal relationship. Take HH and 3xian for instant, HH is 3xian’s master and, at the same time, 3xian is HH’s master,which is quite illegal! To avoid this,please help us to judge whether their relationship is legal or not.

Please note that the "master and prentice" relation is transitive. It means that if A is B’s master ans B is C’s master, then A is C’s master.

输入:

The input consists of several test cases. For each case, the first line contains two integers, N (members to be tested) and M (relationships to be tested)(2 <= N, M <= 100). Then M lines follow, each contains a pair of (x, y) which means x is y’s master and y is x’s prentice. The input is terminated by N = 0.
TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,…, N-1). We use their numbers instead of their names.

输出:

The input consists of several test cases. For each case, the first line contains two integers, N (members to be tested) and M (relationships to be tested)(2 <= N, M <= 100). Then M lines follow, each contains a pair of (x, y) which means x is y’s master and y is x’s prentice. The input is terminated by N = 0.
TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,…, N-1). We use their numbers instead of their names.

样例输入:

3 2
0 1
1 2
2 2
0 1
1 0
0 0

样例输出:

YES
NO

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxx=105;
//degree[]	每个结点的入度
//f[]	每个结点所在的层
int degree[maxx];
int f[maxx];
int map[maxx][maxx];
int top;
int n,m;
bool Toplogical_sort()
{
    int i,j;
    bool p=true;
    top=0;
    int tmp=0;
    while(p)
    {

        p=false;
        top++;
        tmp=-1;
        for(i=0; i<=n-1; i++)
            if(degree[i]==0)
            {
                p=true;
                f[i]=top;
                tmp=i;
                break;
            }
        if(tmp==-1)
            continue;
        for(j=0; j<n; j++)
        {
            if(map[tmp][j])
                degree[j]--;
            degree[tmp]=-1;
        }
    }
    top--;
    if(top<n)
        return false;
    return true;
}
int main()
{
    while(scanf("%d%d",&n,&m))
    {
        if(n==0)
        break;
        memset(map,0,sizeof(map));
        memset(f,0,sizeof(f));
        memset(degree,0,sizeof(degree));
        int a,b;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&a,&b);
            if(!map[a][b])
            {
                map[a][b]=1;
                degree[b]++;
            }
        }
        if(Toplogical_sort())
        {
            printf("YES\n");
        }
        else printf("NO\n");
    }
    return 0;
}

参考:http://blog.csdn.net/sdjzli/article/details/8639420


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks