# UVALive8456 The Maximum Unreachable Node Set（floyd传递闭包+二分图最大匹配）

## The Maximum Unreachable Node Set

In this problem, we would like to talk about unreachable sets of a directed acyclic graph G = (V,E). In mathematics a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is a graph such that there is no way to start at any node and follow a consistently-directed sequence of edges in E that eventually loops back to the beginning again.

A node set denoted by $V_{U}R⊂V$ containing several nodes is known as an unreachable node set of G if, for each two different nodes u and v in $V_{UR}$, there is no way to start at u and follow a consistently-directed sequence of edges in E that finally archives the node v. You are asked in this problem to calculate the size of the maximum unreachable node set of a given graph G.

### Input

The input contains several test cases and the first line contains an integer T(1≤T≤500) which is the number of test cases.

For each case, the first line contains two integers nn(1≤n≤100) and m(0≤m≤n(n−1)/2) indicating the number of nodes and the number of edges in the graph G. Each of the following mm lines describes a directed edge with two integers u and v (1≤u,v≤n and u≠v) indicating an edge from the u-th node to the v-th node. All edges provided in this case are distinct.

We guarantee that all directed graphs given in input are DAGs and the sum of m in input is smaller than 500000.

### Output

For each test case, output an integer in a line which is the size of the maximum unreachable node set of GG.

#### 样例输入

3
4 4
1 2
1 3
2 4
3 4
4 3
1 2
2 3
3 4
6 5
1 2
4 2
6 2
2 3
2 5

### 样例输出

2
1
3

——传送门

### 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;
int G[maxn][maxn];
int n, m;
bool used[maxn];

void floyd()
{
for (int k = 1; k <= n; ++k)
{
for (int i = 1; i <= n; ++i)
{
if (G[i][k])
{
for (int j = 1; j <= n; ++j)
if (G[k][j])
G[i][j] = 1;
}
}
}
}

//void floyd()
//{
//    for (int k = 1; k <= n; ++k)
//        for (int i = 1; i <= n; ++i)
//            for (int j = 1; j <= n; ++j)
//                G[i][j] |= G[i][k] & G[k][j];
//}

bool dfs(int u)
{
for (int i = 1; i <= n; ++i)
{
if (G[u][i] && !used[i])
{
used[i] = true;
{
return true;
}
}
}
return false;
}

int solve()
{
int res = 0;
for (int i = 1; i <= n; ++i)
{
memset(used, 0, sizeof(used));
if (dfs(i))
++res;
}
return res;
}

int main()
{
int T, u, v;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
memset(G, 0, sizeof(G));
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &u, &v);
G[u][v] = 1;
}
floyd();
int ans = n - solve();
printf("%d\n", ans);
}
return 0;
}

Vjudge上交UVALive一直WA，找网上的代码也是WA，后面看了一下提交记录，貌似没有过的，玄学，可以去计蒜客或者中国石油大学OJ上交。

The end.
2018-08-24 星期五