%% ### 题目描述
给你一张有向图 \(G\)，求一个结点数最大的结点集，使得该结点集中的任意两个结点 \(u\) 和 \(v\) 满足：要么 \(u\) 可以达 \(v\)，要么 \(v\) 可以达 \(u\) （\(u,v\) 相互可达也行）。
输入格式
第一行，输入一个整数，代表测试数据组数 \(T\)，每组数据的格式如下。
第一行为结点数 \(n\) 和边数 \(m\)，结点编号 \(1 \sim n\)。
以下 \(m\) 行每行两个整数 \(u\) 和 \(v\) ，表示一条有向边 \(u \to v\)。
输出格式
对于每组数据，输出最大结点集的结点数。 %%
原题 PDF
Description
给定一个有向图 \(G\)，考虑以下转换。 首先，创建一个新图 \(T (G)\)，其顶点集与 \(G\) 相同。如果 \(G\) 中存在从 \(u\) 到 \(v\) 的路径只按照正向方向连通，则在 \(T (G)\)中创建从顶点 \(u\) 到顶点 \(v\) 的有向边。这个图 \(T(G)\)通常被称为 \(G\) 的传递闭包。 我们定义有向图中的团为顶点集 \(U\)，使得对于 \(U\) 中的任意两个顶点 \(u\) 和 \(v\)，从 \(u\) 到 \(v\) 或者从 \(v\) 到 \(u\)（或者两者都有）存在有向边。团的大小是指团中顶点的数量。
Input
输入的第一行给出了案例的数量。 每个测试案例描述了一个图 \(G\)。 它以两个整数 \(n\) 和 \(m\) 开头，其中 G 的顶点数 (\(0≤ n ≤ 1000\))， G 的有向边的数量 \((0≤ m ≤ 50,000)\)。\(G\) 的顶点从 \(1\) 到 \(n\) 编号。 接下来的 \(m\) 行包含两个不同的整数 \(u\) 和 \(v\)，它们在 \(1\) 到 \(n\) 之间，定义了 \(G\) 中从 \(u\) 到 \(v\) 的有向边。
Output
对于每个测试案例，输出一个整数，表示 \(T (G)\) 中最大团的大小。
Sample Input
1 | 1 |
Sample Output
1 | 4 |
代码
Tarjan+记忆化搜索 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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
using namespace std;
const int N = 1010;
vector<int> e[N],e2[N];
int n, m, t, dfn[N], low[N], instk[N], siz[N], scc[N], stk[N], top, tot, cnt, in[N], out[N], maxsum[N];
void tarjan(int x)
{
dfn[x] = low[x] = ++tot;
stk[++top] = x;
instk[x] = 1;
for (int y : e[x])
{ //邻接表存图
if (!dfn[y])
{
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if (instk[y])
{
low[x] = min(low[x], low[y]);
}
}
if (dfn[x] == low[x])
{
int y;
++cnt;
do
{
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;
++siz[cnt];
} while (y != x);
}
}
void dfs(int u)
{
if (maxsum[u] != -1)
return;
maxsum[u] = siz[u];
for (int v : e2[u])
{
dfs(v);
maxsum[u] = max(maxsum[u], siz[u] + maxsum[v]);
}
}
void solve()
{
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(scc, 0, sizeof scc);
memset(siz, 0, sizeof siz);
memset(instk, 0, sizeof instk);
memset(stk, 0, sizeof stk);
memset(in, 0, sizeof in);
memset(out, 0, sizeof out);
memset(maxsum, -1, sizeof maxsum);
for (int i = 1; i <= n; i++)
e[i].clear(),e2[i].clear();
cnt = 0, tot = 0, top = 0;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
e[a].push_back(b);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= n; i++)//重新构建缩点之后的图
{
for (int j : e[i])
{
if (scc[i] != scc[j])
{
e2[scc[i]].push_back(scc[j]);
in[scc[j]]++;
out[scc[i]]++;
}
}
}
int ans = 0;
for (int i = 1; i <= cnt; i++)
{
if (!in[i])
{
dfs(i);
ans = max(ans, maxsum[i]);
}
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> t;
while (t--)
solve();
}