[TIOJ 1683][UVa 11324] 最大集團 The Largest Clique

作法：

題目要找一個最大的點集，使得在裡面的任兩點 x , y ，有 x 可以走到 y 或是 y 可以走到 x 。首先可以發現在同一個SCC( 強連通分量 )裡面的點要嘛是全部選，要嘛是都不選，因為裡面任兩點互通，所以如果考慮先把SCC縮起來之後，就變成了一個每個點都有點權的DAG，並且我們要在上面找一個點權和最大的且任兩點都有一點可以到另外一點的子集。這個問題看起來很難，但實際上會等價於「DAG上點權和最大的路徑」。因為如果考慮對我們選好的子集拓墣排序，得到了 P1 , ... , Pk ，那麼 Pi 和 P( i+1 ) 的關係一定是 Pi 可以走到 P( i+1 ) ( 如果是反過來，那就和拓樸排序的定義矛盾 )，而如果 Pi 和 P( i+1 ) 之間沒有連一條邊的話，那把他們之間的路徑經過的點再加進來會更好，矛盾。所以我們要找的就是一條DAG上的路徑，這就可以簡單的用記憶化DP解決了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10 ;
 
vector<int> v1[maxn],v2[maxn],v[maxn] ;
bool vis[maxn] ;
int t,topo[maxn],scnt,scc[maxn] ;
int sz[maxn] ;
 
void dfs1(int x)
{
    vis[x]=1 ;
    for(auto i : v1[x]) if(!vis[i])
        dfs1(i) ;
    topo[--t]=x ;
}
 
void dfs2(int x)
{
    vis[x]=1 ; scc[x]=scnt ;
    sz[scnt]++ ;
    for(auto i : v2[x]) if(!vis[i])
        dfs2(i) ;
}
 
int d[maxn] ;
int dp(int x)
{
    if(d[x]!=-1) return d[x] ;
    int &ans=d[x] ; ans=sz[x] ;
    for(auto i : v[x]) ans=max(ans,sz[x]+dp(i)) ;
    return ans ;
}
 
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        int n,m ; scanf("%d%d",&n,&m) ;
        for(int i=1;i<=n;i++)
            v1[i].clear() , v2[i].clear() , v[i].clear() ;
        memset(sz,0,sizeof(sz)) ;
        while(m--)
        {
            int x,y ; scanf("%d%d",&x,&y) ;
            v1[x].push_back(y) ;
            v2[y].push_back(x) ;
        }
 
        t=n+1 ;
        memset(vis,0,sizeof(vis)) ;
        for(int i=1;i<=n;i++) if(!vis[i])
            dfs1(i) ;
 
        scnt=0 ;
        memset(vis,0,sizeof(vis)) ;
        for(int i=1;i<=n;i++) if(!vis[topo[i]])
            scnt++ , dfs2(topo[i]) ;
 
        for(int i=1;i<=n;i++) for(auto j : v1[i])
            if(scc[i]!=scc[j]) v[scc[i]].push_back(scc[j]) ;
 
        for(int i=1;i<=scnt;i++)
            sort(v[i].begin(),v[i].end()) ,
            v[i].resize(unique(v[i].begin(),v[i].end())-v[i].begin()) ;
 
        int ans=0 ;
        memset(d,-1,sizeof(d)) ;
        for(int i=1;i<=scnt;i++) ans=max(ans,dp(i)) ;
        printf("%d\n",ans) ;
    }
}