uva11324 The Largest Clique --- 强连通+dp-白红宇

给一个有向图G，求一个子图要求当中随意两点至少有一边可达。

问这个子图中最多含多少个顶点。

首先找SCC缩点建图。每一个点的权值就是该点包括点的个数。

要求当中随意两点可达，实际上全部边仅仅能同方向，不然一定有两点不可达，

这样题目又转换成求DAG图最长路的问题了。

然后从入度为0的点開始记忆化搜索。dp[i]表示以i为根最多包括多少点。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #define inf 0x3f3f3f3f#define eps 1e-6#define ll __int64#define M 1010using namespace std;int sta[M],top; //Tarjan 算法中的栈bool vis[M]; //检查是否在栈中int dfn[M]; //深度优先搜索訪问次序int low[M]; //能追溯到的最早的次序int ccnt; //有向图强连通分量个数int id; //索引號vector
             
               e[M]; //邻接表表示vector
              
                part[M]; //获得强连通分量结果int inpart[M]; //记录每一个点在第几号强连通分量里int degree[M]; //记录每一个强连通分量的度vector
               
                 edge[M];//缩点后建图int ans,n,m,dp[M],in[M],point[M];void tarjan(int x){ int i,j; dfn[x]=low[x]=id++; vis[x]=1; sta[++top]=x; for(i=0;i

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5364945.html，如需转载请自行联系原作者