判斷給定圖是否存在合法的拓撲排序

http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2140&cid=1186

就是判斷圖中是否存在有向環，如果存在，則不是拓撲排序。

1.借助dfs函數判斷是否存在環

#include<stdio.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 11

int G[maxn][maxn],vis[maxn],n;

int DFS(int u)
{
    vis[u]=-1;//正在通路
    for(int v=1; v<=n; v++)
        if(G[u][v])
        {
            if(vis[v]<0)//判斷是否有環
                return 0;
            if(!vis[v] && !DFS(v))
                return 0;
        }
    vis[u]=1;//已通路過
    return 1;
}

int toposort()
{
    for(int u=1; u<=n; u++)
        if(!vis[u] && !DFS(u))
            return 0;
    return 1;
}

int main()
{
    int m,u,v;
    while(~scanf("%d%d",&n,&m) && n+m!=0)
    {
        memset(G,0,sizeof(G));
        memset(vis,0,sizeof(vis));
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&u,&v);
            G[u][v]=1;
        }
        if(toposort())
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;
}
           

　　

2.根據是否有前驅點判斷是否尋在環

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 11

int G[maxn][maxn],vis[maxn],n;

int main()
{
    int m,u,v;
    while(~scanf("%d%d",&n,&m) && n+m!=0)
    {
        int bug=0;
        memset(G,0,sizeof(G));
        memset(vis,0,sizeof(vis));
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&u,&v);
            G[u][v]=1;
            vis[v]++;//入度
        }
        for(int i=0; i<n; i++)//總控
        {
            int flag=0;
            for(u=1; u<=n; u++)
                if(vis[u]==0)
                {
                    flag=1;
                    vis[u]--;//已被通路标記（該值為-1）
                    for(v=1; v<=n; v++)
                        if(G[u][v])
                            vis[v]--;//将關聯的頂點的入讀減1
                    break;
                }
            if(!flag)//存在環
            {
                bug=1;
                break;
            }
        }
        if(bug)
        printf("NO\n");
        else
        printf("YES\n");
    }

    return 0;
}
           

　　

　　

　　

轉載于:https://www.cnblogs.com/guoyongzhi/p/3233006.html