MENU

UVALive8456 The Maximum Unreachable Node Set(floyd传递闭包+二分图最大匹配)

2018 年 08 月 24 日 • 阅读: 1175 • 图论阅读设置

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

链接

题意

给定一个有向无环图,求最大不可到达的点集(对于集合中任意两点u、v,不能从点u出发到达点v)。

题解

使用Floyd求传递闭包得到可达矩阵,然后跑一遍二分图最大匹配,答案就是顶点数减去二分图最大匹配。其实就是顶点数减去最小路径覆盖,有点最大独立集的感觉。

二分图:任意一张图,若能将所有顶点分为两个互斥的集合,每个集合内的点两两互不相连,则可看做二分图(二部图)

根据题意,计算图的可达性矩阵,用此矩阵作为二分图,就可用匈牙利算法算出二分图的最大匹配数res,注意res是匹配成功的有向边的数目,所以最多有res个点可以被到达(或者说有res个点可以出去)不能被到达的点,就可以抠出来,作为符合本题的那个点集合。

另一种理解,匹配完边之后,有n-res个点没有被到达,也就是可以有从这n-res个点起始的n-res条路(平行的),从这n-res条路上各取一点,必定互不相连,故答案为n-res。

——传送门

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;
int G[maxn][maxn];
int n, m;
int linker[maxn];
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;
            if (linker[i] == -1 || dfs(linker[i]))
            {
                linker[i] = u;
                return true;
            }
        }
    }
    return false;
}

int solve()
{
    int res = 0;
    memset(linker, -1, sizeof(linker));
    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 星期五