图结构练习——判断给定图是否存在合法拓扑序列

Time Limit: 1000MS MemoryLimit: 65536KB

SubmitStatistic

ProblemDescription

 给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。

Input

 输入包含多组，每组格式如下。

第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10)

后面m行每行两个整数a b，表示从a到b有一条有向边。

 

Output

 若给定有向图存在合法拓扑序列，则输出YES；否则输出NO。

 

ExampleInput

1 0

2 2

1 2

2 1

ExampleOutput

YES

NO

Hint

 

Author

 赵利强

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m;
int tu[30][30],vis[30],du[30];
bool toposort()
{
    int i,j,f;
    for(i=1; i<=n; i++)//依次访问寻找n个节点
    {
        f = 0;//用来标记找到还是没找到
        for(j=1; j<=n; j++)//每次仅查找访问最先被找到的（未被访问）但入度为0的点
        {
            if(du[j]==0&&vis[j]==0)
            {
                vis[j] = 1;
                for(int k=1; k<=n; k++)//找到之后，把每个与之相连的顶点入度减一
                {
                    if(tu[j][k])
                        du[k]--;
                }
                f = 1;//每次目的只是找到一个，找到之后即可以终止
                break;
            }
        }
        if(f==0)//当出现环时，则无法找到入度为0的点，此时剪枝立即退出
        break;
    }
    if(f) return true;
    else return false;
}
int main()
{

    int a,b;
    while(~scanf("%d%d",&n,&m))
    {
        memset(tu,0,sizeof(tu));
        memset(du,0,sizeof(du));
        memset(vis,0,sizeof(vis));
        while(m--)
        {
            cin>>a>>b;
            tu[a][b] = 1;
            du[b]++;
        }
        if(toposort())cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}


/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 0ms
Take Memory: 168KB
Submit time: 2017-02-20 10:32:32
****************************************************/