The Largest Clique
题意：有向图最大团。求任意两点可达（不是互达）的最多点数。
先求出SCC，然后缩点，新图就变成了一个DAG，每个点的权值为内点的个数，用DP求解最大值。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxv=1010; 4 5 int n,m; 6 7 vector<int> G[maxv]; 8 int pre[maxv],lowlink[maxv],sccno[maxv],dfsk,scc_cnt; 9 stack<int> s; 10 11 void dfs(int u){ 12 pre[u]=lowlink[u]=++dfsk; 13 s.push(u); 14 for(int i=0;i<G[u].size();i++){ 15 int v=G[u][i]; 16 if(!pre[v]){ 17 dfs(v); 18 lowlink[u]=min(lowlink[u],lowlink[v]); 19 } 20 else if(!sccno[v]) lowlink[u]=min(lowlink[u],lowlink[v]); 21 } 22 if(lowlink[u]==pre[u]){ 23 scc_cnt++; 24 for(;;){ 25 int x=s.top(); 26 s.pop(); 27 sccno[x]=scc_cnt; 28 if(x==u) break; 29 } 30 } 31 } 32 void find_scc(int n){ 33 memset(pre,0,sizeof(pre)); 34 memset(lowlink,0,sizeof(lowlink)); 35 memset(sccno,0,sizeof(sccno)); 36 dfsk=scc_cnt=0; 37 for(int i=0;i<n;i++) if(!pre[i]) dfs(i); 38 } 39 40 int sz[maxv],d[maxv],TG[maxv][maxv]; //DP 41 int dp(int u){ 42 if(d[u]>0) return d[u]; 43 d[u]=sz[u]; 44 for(int i=1;i<=scc_cnt;i++) 45 if(TG[u][i]&&u!=i) d[u]=max(d[u],dp(i)+sz[u]); 46 return d[u]; 47 } 48 int main(){ 49 int t; 50 scanf("%d",&t); 51 while(t--){ 52 scanf("%d%d",&n,&m); 53 for(int i=0;i<n;i++) G[i].clear(); 54 int u,v; 55 for(int i=0;i<m;i++){ 56 scanf("%d%d",&u,&v); 57 u--;v--; 58 G[u].push_back(v); 59 } 60 find_scc(n); 61 62 //DP 63 memset(d,-1,sizeof(d)); 64 memset(sz,0,sizeof(sz)); 65 memset(TG,0,sizeof(TG)); 66 for(int i=0;i<n;i++) 67 { 68 sz[sccno[i]]++; //新图各点权重 69 for(int j=0;j<G[i].size();j++) 70 TG[sccno[i]][sccno[G[i][j]]]=1; //新图 71 } 72 int ans=0; 73 for(int i=1;i<=scc_cnt;i++) 74 ans=max(ans,dp(i)); 75 printf("%d ",ans); 76 } 77 }