圖結構練習——判斷給定圖是否存在合法拓撲序列

Time Limit: 1000MS Memory limit: 65536K

題目描述

 給定一個有向圖，判斷該有向圖是否存在一個合法的拓撲序列。

輸入

 輸入包含多組，每組格式如下。 第一行包含兩個整數n，m，分别代表該有向圖的頂點數和邊數。(n<=10) 後面m行每行兩個整數a b，表示從a到b有一條有向邊。  

輸出

 若給定有向圖存在合法拓撲序列，則輸出YES；否則輸出NO。  

示例輸入

1 0
2 2
1 2
2 1
      

示例輸出

YES
NO      

1. 進行拓撲排序的方法：

(1). 在有向圖中選一個沒有前驅的頂點且輸出之。

(2). 從圖中删除該頂點和所有以它為尾的弧。

(3). 重複上述兩步，直至全部頂點均已輸出，或者目前圖中不存在無前驅的頂點為止。後一種情況說明圖中有環。

2. 在計算機中可以采用鄰接表做有向圖的存儲結構，且增加一個存放頂點入度的數組(indegree)。

入度為零的結點即為沒有前驅的頂點，删除頂點以及以它為尾的弧的操作，則可換以弧頭頂點的入度減1來實作。

為了避免重複檢測入度為零的頂點，另設一棧暫存所有入度為零的頂點。

#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <string.h>
using namespace std;
typedef struct arcnode//表結點
{
    int adj;
    struct arcnode *next;
} arcnode;
typedef struct vnode//頭結點
{
    int data;
    arcnode *first;
} adjlist[100];
typedef struct
{
    adjlist a;
    int vn, an;
} ALG;
int n, m;
int indegree[100];//記錄每個點的入度
void create(ALG &g)
{
    int i, j, v1, v2;
    arcnode *p;
    for(i=1; i<=n; i++)
    {
        g.a[i].first = NULL; //頭結點清空
    }
    for(i=1; i<=m; i++)
    {
        scanf("%d %d", &v1, &v2);
        p = new arcnode;
        p->adj = v2;
        indegree[v2]++;
        p->next = g.a[v1].first;
        g.a[v1].first = p;
    }
}

void topo(ALG &g)
{

    int i, j, k;
    arcnode *p;
    stack <int> s;

    for(i=1; i<=n; i++)//入度為0的結點入棧
        if(!indegree[i])
            s.push(i);

    int count = 0;//記錄出棧頂點個數
    while(!s.empty())
    {
        j = s.top();
        s.pop();
        count++;
        for(p=g.a[j].first; p; p=p->next) //删去所有已j為起點的出邊
        {
            k = p->adj;
            if(!(--indegree[k]))//将新入度為0的結點入棧
                s.push(k);
        }
    }
    if(count<n)
        printf("NO\n");
    else
        printf("YES\n");
}

int main()
{
    ALG g;
    while(~scanf("%d %d", &n, &m))
    {
        memset(indegree, 0, sizeof(indegree));
        create(g);
        topo(g);
    }
    return 0;
}