图

图

描述

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

输入

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

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

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

保证没有自环和重边。

输

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

样例 1 输入

2

32

12

23

32

12

13

样例 1 输

样例 1 解释

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

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

样例 2

请查看下发文件内的 sample2_input.txt 和 sample2_output.txt。

限制

对于 50%的数据，n, m ≤ 100；

对于 100%的数据，T ≤ 100, n, m ≤ 10000。时间：4 sec

空间：512 MB

提示

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

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

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

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

代码

#include <bits/stdc++.h> using namespace std; #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;

}

// ================= 代码实现结束 =================

int main() {

    int T;

    for (scanf("%d", &T); T--; ) {

        scanf("%d%d", &n, &m);

        for (int i = 1; i <= n; ++i) {

            in[i] = 0;

            e[i].clear();

        }

        for (int i = 0; i < m; ++i) {

            int x, y;

            scanf("%d%d", &x, &y);

            e[x].push_back(y);

            ++in[y];

        }

        printf("%d\n", getAnswer());

    }

    return 0;

}