UVA-11324 有向图最大团 The Largest Clique (Tarjian求强连通分量 + DAG 上 DP)

​​UVA-11324 The Largest Clique​​

题目

给定一张有向图G，求一个节点数目最大的节点集，使得该集合中的任意两个节点u和v满足：要么u可以到达v，要么v可以到达u（u,v相互可达也算满足），要求输出最大的节点数

分析

在强连通子图里，任何两个点两两可达，先求图中所有强连通分量，缩点，之后每个缩点组成了一张

图，那么问题就转变成了求

代码

#include <bits/stdc++.h>
using namespace std;
#define d(x) cout<<(x)<<endl
const int N = 1e3 + 10;

int _, n, m;
vector<int> g[N];
int pre[N], low[N], sccno[N], dfs_clock, scc_cnt;
stack<int> s;

void dfs(int u){
    pre[u] = low[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);
            low[u] = min(low[u], low[v]);
        }else if(!sccno[v])
            low[u] = min(low[u], pre[v]);
    }
    if(low[u] == pre[u]){
        scc_cnt++;
        while(1){
            int x = s.top();
            s.pop();
            sccno[x] = scc_cnt;
            if(x == u)
                break;
        }
    }
}

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

int size[N], e[N][N], dp[N];
int DP(int u){
    int &ans = dp[u];
    if(ans >= 0)
        return ans;
    ans = size[u];      // 当前节点权值     
    for(int v = 1; v <= scc_cnt; v++){  // 遍历 u 所有子节点
        if(u != v && e[u][v])
            ans = max(ans, DP(v) + size[u]);
    }
    return ans;
}

int main()
{
    for (scanf("%d", &_); _; _--){
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++)
            g[i].clear();
        for(int i = 0, u, v; i < m; i++){
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
        }
        find_scc();        // 找强连通分量

        memset(size, 0, sizeof size);
        memset(e, 0, sizeof e);
        for(int i = 1; i <= n; i++){
            size[sccno[i]]++;         // 求DAG上每个点权值
            for (int j = 0; j < g[i].size(); j++)
                e[sccno[i]][sccno[g[i][j]]] = 1;
                // 构造 SCC 图
        }
        int ans = 0;
        memset(dp, -1, sizeof dp);
        // 从每个点开始
        for(int i = 1; i <= scc_cnt; i++){
            ans = max(ans, DP(i));      // 1 ~~ scc_cnt
        }
        printf("%d\n", ans);
    }
    return 0;
}      

用邻接表写就错。。。

#include <bits/stdc++.h>
using namespace std;
#define d(x) cout<<(x)<<endl
const int N = 1e3 + 10;

int _, n, m;
int h[N], to[N], ne[N], idx;
int pre[N], low[N], sccno[N], dfs_clock, scc_cnt;
stack<int> s;

inline void add(int a, int b){
    to[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u){
    pre[u] = low[u] = ++dfs_clock;
    s.push(u);
    for(int i = h[u]; ~i; i = ne[i]){
        int v = to[i];
        if(!pre[v]){
            dfs(v);
            low[u] = min(low[u], low[v]);
        }else if(!sccno[v])
            low[u] = min(low[u], pre[v]);
    }
    if(low[u] == pre[u]){
        scc_cnt++;
        while(1){
            int x = s.top();
            s.pop();
            sccno[x] = scc_cnt;
            if(x == u)
                break;
        }
    }
}

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

int size[N], e[N][N], dp[N];
int DP(int u){
    int &ans = dp[u];
    if(ans >= 0)
        return ans;
    ans = size[u];      // 当前节点权值     
    for(int v = 1; v <= scc_cnt; v++){  // 遍历 u 所有子节点
        if(u != v && e[u][v])
            ans = max(ans, DP(v) + size[u]);
    }
    return ans;
}

int main()
{
    for (scanf("%d", &_); _; _--){
        scanf("%d%d", &n, &m);
        memset(h, -1, sizeof h);
        while(!s.empty())
            s.pop();
        idx = 0;
        for(int i = 0, u, v; i < m; i++){
            scanf("%d%d", &u, &v);
            // u--, v--;
            add(u, v);
        }
        find_scc();        // 找强连通分量

        memset(size, 0, sizeof size);
        memset(e, 0, sizeof e);
        for(int i = 1; i <= n; i++){
            size[sccno[i]]++;         // 求DAG上每个点权值
            for (int j = h[i]; ~j; j = ne[j])
                e[sccno[i]][sccno[to[j]]] = 1;
                // 构造 SCC 图
        }
        int ans = 0;
        memset(dp, -1, sizeof dp);
        // 从每个点开始
        
        for(int i = 1; i <= scc_cnt; i++){
            ans = max(ans, DP(i));      // 1 ~~ scc_cnt
            // cout << ans << endl;
        }
        printf("%d\n", ans);
    }
    return 0;
}