The Maximum Unreachable Node Set

190 阅读 0 评论 126 点赞

我是靠谱客的博主搞怪冬天，这篇文章主要介绍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 $(D A G)$ 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_UR subset 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 \leq T \leq 500)$ which is the number of test cases.

For each case, the first line contains two integers $n (1 \leq n \leq 100)$ and $m (0 \leq m \leq n (n - 1) / 2)$ indicating the number of nodes and the number of edges in the graph $G$ . Each of the following $m$ lines describes a directed edge with two integers $u$ and $v (1 \leq u, v \leq n$ and $u \neq 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 $G$ .

样例输入

复制代码

样例输出

复制代码

题意：给你一张有向无环图，问最多可以取出多少个点，使得它们两两之间不能到达

解题思路：先floyd处理出能两两之间到达的点，然后二分图跑最大匹配，最后n-ans就是答案

复制代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;
int n, m;
int x[109], y[109], mp[109][109];
int s[109], nt[10050], e[10050];
int visit[125];
bool path(int k)
{
for (int i = s[k]; ~i; i = nt[i])
{
int ee = e[i];
if (!visit[ee])
{
visit[ee] = 1;
if (y[ee] == -1 || path(y[ee]))
{
y[ee] = k;
x[k] = ee;
return 1;
}
}
}
return 0;
}
void MaxMatch()
{
int ans = 0;
memset(x, -1, sizeof x);
memset(y, -1, sizeof y);
for (int i = 1; i <= n; i++)
{
if (x[i] == -1)
{
memset(visit, 0, sizeof visit);
if (path(i)) ans++;
}
}
printf("%dn", n - ans);
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d %d", &n, &m);
int cnt = 1, u, v;
memset(s, -1, sizeof s);
memset(mp, 0, sizeof mp);
for (int i = 1; i <= m; i++)
{
scanf("%d %d", &u, &v);
mp[u][v] = 1;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (mp[i][k] && mp[k][j]) mp[i][j] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (mp[i][j])
{
nt[cnt] = s[i], s[i] = cnt, e[cnt++] = j;
}
MaxMatch();
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;
int n, m;
int x[109], y[109], mp[109][109];
int s[109], nt[10050], e[10050];
int visit[125];
bool path(int k)
{
for (int i = s[k]; ~i; i = nt[i])
{
int ee = e[i];
if (!visit[ee])
{
visit[ee] = 1;
if (y[ee] == -1 || path(y[ee]))
{
y[ee] = k;
x[k] = ee;
return 1;
}
}
}
return 0;
}
void MaxMatch()
{
int ans = 0;
memset(x, -1, sizeof x);
memset(y, -1, sizeof y);
for (int i = 1; i <= n; i++)
{
if (x[i] == -1)
{
memset(visit, 0, sizeof visit);
if (path(i)) ans++;
}
}
printf("%dn", n - ans);
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d %d", &n, &m);
int cnt = 1, u, v;
memset(s, -1, sizeof s);
memset(mp, 0, sizeof mp);
for (int i = 1; i <= m; i++)
{
scanf("%d %d", &u, &v);
mp[u][v] = 1;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (mp[i][k] && mp[k][j]) mp[i][j] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (mp[i][j])
{
nt[cnt] = s[i], s[i] = cnt, e[cnt++] = j;
}
MaxMatch();
}
return 0;
}