UVa 11324 最大团（强连通分量缩点）

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

思路：

找到SCC后进行缩点建图，每个点的权值则为其连通分量的点数，这样就是找DAG上一条最大路径，DP解决。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<stack>
  7 #include<queue>
  8 #include<cmath>
  9 using namespace std;
 10 
 11 const int maxn=1000+5;
 12 
 13 int n,m;
 14 
 15 vector<int> G[maxn];
 16 int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
 17 int num[maxn];
 18 int map[maxn][maxn];
 19 int d[maxn];
 20 stack<int> S;
 21 
 22 void dfs(int u)
 23 {
 24     pre[u]=lowlink[u]=++dfs_clock;
 25     S.push(u);
 26     for(int i=0;i<G[u].size();i++)
 27     {
 28         int v=G[u][i];
 29         if(!pre[v])
 30         {
 31             dfs(v);
 32             lowlink[u]=min(lowlink[u],lowlink[v]);
 33         }
 34         else if(!sccno[v])
 35         {
 36             lowlink[u]=min(lowlink[u],pre[v]);
 37         }
 38     }
 39     if(lowlink[u]==pre[u])
 40     {
 41         scc_cnt++;
 42         for(;;)
 43         {
 44             int x=S.top(); S.pop();
 45             sccno[x]=scc_cnt;
 46             if(x==u)  break;
 47         }
 48     }
 49 }
 50 
 51 void find_scc()
 52 {
 53     dfs_clock=scc_cnt=0;
 54     memset(sccno,0,sizeof(sccno));
 55     memset(pre,0,sizeof(pre));
 56     for(int i=0;i<n;i++)
 57         if(!pre[i])  dfs(i);
 58 }
 59 
 60 int dp(int u)
 61 {
 62     int& ans=d[u];
 63     if(ans!=-1)   return ans;
 64     ans=num[u];
 65     for(int i=1;i<=scc_cnt;i++)
 66     {
 67         if(i!=u && map[u][i])   ans=max(ans,num[u]+dp(i));
 68     }
 69     return ans;
 70 }
 71 
 72 int main()
 73 {
 74     //freopen("D:\input.txt","r",stdin);
 75     int T;
 76     scanf("%d",&T);
 77     while(T--)
 78     {
 79         scanf("%d%d",&n,&m);
 80         for(int i=0;i<n;i++)  G[i].clear();
 81         while(m--)
 82         {
 83             int u,v;
 84             scanf("%d%d",&u,&v);
 85             u--; v--;
 86             G[u].push_back(v);
 87         }
 88         find_scc();
 89         memset(num,0,sizeof(num));
 90         memset(map,0,sizeof(map));
 91         for(int i=0;i<n;i++)
 92             num[sccno[i]]++;
 93         for(int u=0;u<n;u++)
 94         {
 95             for(int i=0;i<G[u].size();i++)
 96             {
 97                 int x=sccno[u];
 98                 int y=sccno[G[u][i]];
 99                 map[x][y]=1;
100             }
101         }
102         int ans=0;
103         memset(d,-1,sizeof(d));
104         for(int i=1;i<=scc_cnt;i++)
105             ans=max(ans,dp(i));
106         printf("%d
",ans);
107     }
108     return 0;
109 }