UVA11324 The Largest Clique（Tarjan缩点+DAG图简单dp）

The Largest Clique

Description

Given a directed graph G, consider the following transformation. First, create a new graph T(G) to have the same vertex set as G. Create a directed edge between two vertices u and v in T(G) if and only if there is a path between u and v in G that follows the directed edges only in the forward direction. This graph T(G) is often called the transitive closure of G.

We define a clique in a directed graph as a set of vertices U such that for any two vertices u and v in U, there is a directed edge either from u to v or from v to u (or both). The size of a clique is the number of vertices in the clique.

The number of cases is given on the first line of input. Each test case describes a graph G. It begins with a line of two integers n and m, where 0 ≤ n ≤ 1000 is the number of vertices of G and 0 ≤ m ≤ 50,000 is the number of directed edges of G. The vertices of G are numbered from 1 to n. The following m lines contain two distinct integers u and v between 1 and n which define a directed edge from u to v in G.

For each test case, output a single integer that is the size of the largest clique in T(G).

Sample input

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

Output for sample input

4

链接

https://vjudge.net/problem/UVA-11324

题意

给定一个n点m边的有向图，现要求一个最大点集，要求该点集中的任意两点u、v满足：u可以到达v或者v可以到达u，即$u \rightarrow v $ 或$v \rightarrow u $或$u \rightleftarrows v $ 。

题解

同一个强连通分量中的点要么都选，要么不选。把强连通分量收缩点后得到SCC图，让每个SCC结点的权等于它的结点数，则题目转化为求SCC图上权最大的路径。由于SCC图是一个 DAG， 可以用动态规划求解。

参考自：uva 11324 The Largest Clique（图论-tarjan,动态规划

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
const int maxn = 1010;
vector <int> E[maxn];
vector <int> G[maxn];
int n, m;
int tot, scc_cnt;

int dfn[maxn], low[maxn], sccno[maxn], sccnum[maxn], dp[maxn];
bool vis[maxn];
stack <int> s;

void tarjan(int x) // 求强连通分量
{
    dfn[x] = low[x] = ++tot;
    s.push(x);
    vis[x] = true;
    for (int i = 0; i < G[x].size(); ++i)
    {
        int v = G[x][i];
        if (!dfn[v])
        {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if (vis[v])
            low[x] = min(low[x], dfn[v]);
    }
    if (dfn[x] == low[x])
    {
        ++scc_cnt;
        while (1)
        {
            int u = s.top();
            s.pop();
            vis[u] = 0;
            sccno[u] = scc_cnt;
            sccnum[scc_cnt]++;
            if (u == x)
                break;
        }
    }
}

void find_scc()
{
    memset(vis, 0, sizeof(vis));
    memset(dfn, 0, sizeof(vis));
    memset(low, 0, sizeof(low));
    memset(sccno, 0, sizeof(sccno));
    memset(sccnum, 0, sizeof(sccnum));
    tot = scc_cnt = 0;
    for (int i = 0; i < n; ++i)
        if (!dfn[i])
            tarjan(i);
}

int search(int x) // dp找最大点集
{
    if (dp[x] != -1)
        return dp[x];
    dp[x] = sccnum[x];
    for (int i = 0; i < E[x].size(); ++i) 
    {
        int v = E[x][i];
        dp[x] = max(dp[x], search(v) + sccnum[x]);
    }
    return dp[x];
}

int main()
{
    int T, u, v;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i <= n; ++i) // 坑
        {
            G[i].clear(); 
            E[i].clear();
        }
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d", &u, &v);
            u--;
            v--;
            G[u].push_back(v);
        }
        find_scc();
        memset(dp, -1, sizeof(dp));
        for (int u = 0; u < n; ++u) // 缩点建图
        {
            for (int i = 0; i < G[u].size(); ++i)
            {
                int v = G[u][i];
                if (sccno[u] != sccno[v])
                    E[sccno[u]].push_back(sccno[v]);
            }
        }
        int ans = 0;
        for (int i = 1; i <= scc_cnt; ++i)
            ans = max(ans, search(i));
        printf("%d\n", ans);
    }
    return 0;
}

这道题debug了好久，心累。也没想到memset可以直接清vector数组。

The end,
2018-04-24 星期二