算法三十三：图

傷城~ 2022-05-21 09:12 215阅读 0赞

### **描述** ###

一个数列 a 称为合法的当且仅对于所有的位置 i, j（i < j ≤ n），都不存在一条从 aj 点连向 ai 的有向边。现在有很多个有向无环图，请你判断每个图是否只存在**唯一**的合法数列。

### **输入** ###

输入的第一行包含一个正整数 T ，表示数据组数。

对于每组数据，第一行包含两个正整数 n, m，表示图的节点个数和边数。

接下来 m 行，每行包含两个正整数 x, y（x, y ≤ n），表示这个图有一条从 x 到 y 的有向边。

**保证没有自环和重边。**

### **输出** ###

输出 T 行，若所给的图存在唯一的合法数列，输出 1，否则输出 0。

### **样例输入** ###

2
    3 2
    1 2
    2 3
    3 2
    1 2
    1 3

### **样例输出** ###

1
    0

### **样例解释** ###

第一个图只有一个合法数列：1、2、3；

第二个图有两个合法数列：1、2、3 或者 1、3、2。

### **提示** ###

\[本题就是判断一个有向无环图是否存在唯一的拓扑序列。\]

\[回忆一下求拓扑序列是如何做的：每一次都取一个入度为0的点，将这个点取出来放进拓扑序列里，然后将这个点连向的所有点的入度减去1。\]

\[可以发现，在“每一次都取一个入度为0”这一步，若入度为0的点数多于1个，则显然拓扑序不唯一。\]

\[因此按照这个拓扑序算法做一遍就好。\]

### **一. 伪代码** ###

![70][]

### **二. 具体实现** ###

\#include <bits/stdc++.h>  
using namespace std;  
// ================= 代码实现开始 =================  
const int N = 10005;  
// 为了减少复制开销，我们直接读入信息到全局变量中，并统计了每个点的入度到数组in中  
// n, m：点数和边数  
// in：in\[i\]表示点i的入度  
// e：e\[i\]\[j\]表示点i的第j条边指向的点  
int n, m, in\[N\];  
vector<int> e\[N\];  
// 判断所给有向无环图是否存在唯一的合法数列  
// 返回值：若存在返回1；否则返回0。  
bool getAnswer() \{  
 //找到一个入度为0的点。有向无环图中至少存在一个入度为0的点  
//若存在多个入度为0的点，说明合法序列不唯一  
int x = 0;  
for(int i = 1; i <= n; ++i)  
if(in\[i\] == 0)\{  
if(x != 0)//表示入度为0的点不唯一  
return 0;  
x = i;  
\}  
 //x表示的就是图中唯一的入度为0的点，然后去除关联的边  
for(int j=1; j<= n; ++j)\{  
int z = 0;  
for(int i=0; i < (int)e\[x\].size(); ++i)\{  
int y = e\[x\]\[i\];  
\--in\[y\];  
if(in\[y\] == 0)\{  
if(z != 0)  
return 0;  
z = y;  
\}  
\}  
x = z;  
\}  
return 1;  
\}  
// ================= 代码实现结束 =================

[70]: /images/20220521/a903b6372cef4f55ad4cfe8d7ba10fe2.png