训练指南 UVA

layout: post
title: 训练指南 UVA - 11324（双连通分量 + 缩点+ 基础DP）
author: "luowentaoaa"
catalog: true
mathjax: true
tags:
- 双连通分量
- 基础DP
- 图论
- 训练指南

The Largest Clique

UVA - 11324

题意

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

题解

同一个强连通分量中的点要么都选，要么不选。把强连通分量收缩点后得到SCC图，让每个SCC结点的权等于它的结点数，则题目转化为求SCC图上权最大的路径。所以转化成了dp求DAG上的最长路。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
vector<int>G[maxn],g[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt,sccnum[maxn];
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++;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            sccnum[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));
    memset(sccnum,0,sizeof(sccnum));
    for(int i=0;i<n;i++)
        if(!pre[i])dfs(i);
}
int d[maxn];
int dp(int i){
    int &ans=d[i];
    if(ans>=0)return ans;
    ans=sccnum[i];
    for(int j=0;j<g[i].size();j++){
        int v=g[i][j];
        ans=max(ans,dp(v)+sccnum[i]);
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
   // freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=0;i<=n;i++)G[i].clear(),g[i].clear();
        int u,v;
        for(int i=0;i<m;i++){
            cin>>u>>v;
            u--;v--;
            G[u].push_back(v);
        }
        find_scc(n);
        memset(d,-1,sizeof(d));
        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])
                g[sccno[u]].push_back(sccno[v]);
        }
        int ans=0;
        for(int i=1;i<=scc_cnt;i++)
            ans=max(ans,dp(i));
        cout<<ans<<endl;
    }

    return 0;
}