Uva 11324 - The Largest Clique 縮點 求最大團

Problem B: The Largest Clique

Given a directed graph G, consider the following transformation. First, create a new graph T(G) to have the same vertex set as G. Create a directed edge between two vertices u and v in T(G) if and only if there is a path between u and v in G that follows the directed edges only in the forward direction. This graph T(G) is often called the transitive closure of G.

We define a clique in a directed graph as a set of vertices U such that for any two vertices u and v in U, there is a directed edge either from u to v or from v to u (or both). The size of a clique is the number of vertices in the clique.

The number of cases is given on the first line of input. Each test case describes a graph G. It begins with a line of two integers n and m, where 0 ≤ n ≤ 1000 is the number of vertices of G and 0 ≤ m ≤ 50,000 is the number of directed edges of G. The vertices of G are numbered from 1 to n. The following m lines contain two distinct integers u and v between 1 and n which define a directed edge from u to v in G.

For each test case, output a single integer that is the size of the largest clique in T(G).

Sample input

1
5 5
1 2
2 3
3 1
4 1
5 2
      

Output for sample input

4
      

Zachary Friggstad

-----------------------------------------

縮點，求最大團

-----------------------------------------

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxn=1111;
const int INF=1e8;

void dfs(int u);//搜尋求強連通
void find_scc(int n);//求強連通
void tops(int n);//拓撲排序

int w[maxn];//點權
vector<int>a[maxn];//DAG圖
vector<int>G[maxn];//原圖
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;//Tarjan
stack<int> S;//Tarjan
int indegree[maxn];//入度
int ans;
bool hash[maxn][maxn];
//-----Tarjan------

void dfs(int u)
{
    pre[u]=lowlink[u]=++dfs_clock;
    S.push(u);
    int len=G[u].size();
    for (int i=0;i<len;i++)
    {
        int v=G[u][i];
        if (!pre[v])
        {
            dfs(v);
            lowlink[u]=min( lowlink[u], lowlink[v] );
        }
        else if (!sccno[v])
        {
            lowlink[u]=min( lowlink[u], pre[v] );
        }
    }
    if (lowlink[u]==pre[u])
    {
        scc_cnt++;
        while (true)
        {
            int x=S.top();
            S.pop();
            sccno[x]=scc_cnt;
            w[scc_cnt]++;
            if (x==u) break;
        }
    }
}
void find_scc(int n)
{
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    memset(w,0,sizeof(w));
    while (!S.empty()) S.pop();
    for (int i=1;i<=n;i++)
    {
        if (!pre[i]) dfs(i);
    }
}


int f[maxn];
int DP(int u)
{
    int ret=0;
    int sz=a[u].size();
    for (int i=0;i<sz;i++)
    {
        int v=a[u][i];
        ret=max(ret,DP(v));
    }
    f[u]=ret+w[u];
    return f[u];
}


//-----------------

int main()
{
    int T;
    int n,m;
    scanf("%d",&T);
    while (T--)
    {
        //init()
        memset(indegree,0,sizeof(indegree));
        memset(hash,0,sizeof(hash));
        memset(f,0,sizeof(f));
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
        {
            G[i].clear();
            a[i].clear();
        }
        for (int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
        }
        //強連通
        find_scc(n);
        //縮點
        for (int i=1;i<=n;i++)
        {
            int sz=G[i].size();
            for (int j=0;j<sz;j++)
            {
                int v=G[i][j];
                if (sccno[i]!=sccno[v]&&!hash[sccno[i]][sccno[v]])
                {
                    a[sccno[i]].push_back(sccno[v]);
                    hash[sccno[i]][sccno[v]]=true;
                    indegree[sccno[v]]++;
                }
            }
        }
        ans=0;
        for (int i=1;i<=n;i++)
        {
            if (indegree[i]==0)
            {
                ans=max(ans,DP(i));
            }
        }

        //輸出
        printf("%d\n",ans);
    }
    return 0;
}