uva11324 The Largest Clique --- 强连通+dp

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

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

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

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

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

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

#include <iostream>

#include <cstring>

#include <string>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

#define inf 0x3f3f3f3f

#define eps 1e-6

#define ll __int64

#define M 1010

using namespace std;

int sta[M],top;          //Tarjan 算法中的栈

bool vis[M];             //检查是否在栈中

int dfn[M];                  //深度优先搜索訪问次序

int low[M];                  //能追溯到的最早的次序

int ccnt;                //有向图强连通分量个数

int id;                 //索引號

vector<int> e[M];        //邻接表表示

vector<int> part[M];   //获得强连通分量结果

int inpart[M];   //记录每一个点在第几号强连通分量里

int degree[M];     //记录每一个强连通分量的度

vector<int> 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<e[x].size();i++)

    {

        j=e[x][i];

        if(dfn[j]==-1)

        {

            tarjan(j);

            low[x]=min(low[x],low[j]);

        }

        else if(vis[j])

            low[x]=min(low[x],dfn[j]);

    }

    if(dfn[x]==low[x])

    {

        do

        {

            j=sta[top--];

            vis[j]=0;

            part[ccnt].push_back(j);

            inpart[j]=ccnt;

            point[ccnt]++;

        }while(j!=x);

        ccnt++;

    }

}

void solve(int n)

{

    memset(sta,-1,sizeof sta);

    memset(vis,0,sizeof vis);

    memset(dfn,-1,sizeof dfn);

    memset(low,-1,sizeof low);

    memset(point,0,sizeof point);

    top=ccnt=id=0;

    for(int i=1;i<=n;i++)

        if(dfn[i]==-1)

            tarjan(i);

}

int dfs(int x)

{

    if(dp[x]) return dp[x];

    dp[x]=point[x];

    int i;

    for(i=0;i<edge[x].size();i++)

    {

        int tmp=edge[x][i];

        dp[x]=max(dp[x],point[x]+dfs(tmp));

    }

    return dp[x];

}

int main()

{

    int n,m,i,j,a,b,t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        for(i=0;i<=n;i++)

        {

            part[i].clear();

            e[i].clear();

            edge[i].clear();

        }

        while(m--)

        {

            scanf("%d%d",&a,&b);

            e[a].push_back(b);

        }

        solve(n);

        /*printf("ccnt:%d\n",ccnt);

        for(i=0;i<ccnt;i++)

        {

            for(j=0;j<part[i].size();j++)

                printf("%d ",part[i][j]);

            puts("");

        }*/

        memset(in,0,sizeof in);

        for(i=1;i<=n;i++)//枚举原图中的边

        {

            for(j=0;j<e[i].size();j++)

            {

                int a=inpart[i];

                int b=inpart[e[i][j]];//

                if(a!=b)

                {

                    in[b]++;

                    edge[a].push_back(b);

                }

            }

        }

        ans=0;

        memset(dp,0,sizeof dp);

        for(i=0;i<ccnt;i++)//缩点后的图上是从0到ccnt编号的

        {

            if(!in[i])

                ans=max(ans,dfs(i));

        }

        printf("%d\n",ans);

    }

    return 0;

}