The Largest Clique

原题 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\le n\le 1000$)， G 的有向边的数量 $(0\le m\le 50,000)$。$G$ 的顶点从 $1$ 到 $n$ 编号。
接下来的 $m$ 行包含两个不同的整数 $u$ 和 $v$，它们在 $1$ 到 $n$ 之间，定义了 $G$ 中从 $u$ 到 $v$ 的有向边。

Output

对于每个测试案例，输出一个整数，表示 $T(G)$ 中最大团的大小。

Sample Input

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

Sample Output

4

代码

Tarjan+记忆化搜索

#include <bits/stdc++.h>
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();
}