uva 11324 The Largest Clique（强连通分量 + DAG）-摩杜云开发者社区

uva 11324 The Largest Clique

题目大意：给出一个有向图，要求出该图中的最大结点集。结点集满足下列条件，结点集中的每两个点u, v，要么u可以到达v，要么v可以到达u，要么互相可达。

解题思路：在原图的基础上，先求一次强连通分量。然后把每个强连通分量都缩成点之后，可以得到一个有向无环图，然后可以用dp，求出最大嵌套。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <queue>
using namespace std;

typedef long long ll;
const int N = 1005;
int n, m;
int Cnt[N], dp[N];
vector<int> G[N], G2[N];
int pre[N], lowlink[N], sccno[N], dfs_clock, scc_cnt;
stack<int> S;

void dfs(int u) {
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];    
        if (!pre[v]) {
            dfs(v); 
            lowlink[u] = min(lowlink[u], lowlink[v]);
        } else if (!sccno[v]) {
            lowlink[u] = min(lowlink[u], pre[v]);   
        }
    }
    if (lowlink[u] == pre[u]) {
        scc_cnt++;  
        while (1) {
            int x = S.top(); S.pop();
            sccno[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

void find_scc(int n) {
    dfs_clock = scc_cnt = 0;
    memset(sccno, 0, sizeof(sccno));
    memset(pre, 0, sizeof(pre));
    for (int i = 0; i < n; i++) {
        if (!pre[i]) dfs(i);    
    }
}

void input() {
    scanf("%d %d", &n, &m);     
    for (int i = 0; i <= n; i++) {
        G[i].clear();
    }
    int u, v;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v); 
        u--, v--;
        G[u].push_back(v);
    }
}

int DP(int u) {
    if (dp[u]) return dp[u];
    if (G2[u].size() == 0) return dp[u] = Cnt[u];
    int Max = 0;
    for (int i = 0; i < G2[u].size(); i++) {
        int v = G2[u][i];
        Max = max(Max, DP(v));
    }
    return dp[u] = Cnt[u] + Max;
}

void solve() {
    find_scc(n);
    for (int i = 0; i <= scc_cnt; i++) G2[i].clear();
    memset(Cnt, 0, sizeof(Cnt));
    memset(dp, 0, 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]) {
                G2[sccno[u]].push_back(sccno[v]);
            }
        }   
    }
    for (int i = 0; i < n; i++) {
        Cnt[sccno[i]]++;    
    }   
    int Max = 0;
    for (int i = 1; i <= scc_cnt; i++) Max = max(Max, DP(i));
    printf("%d\n", Max);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        input();    
        solve();
    }
    return 0;
}