首页 > 代码库 > UVa11324 - The Largest Clique(DAG+DP+SCC)

UVa11324 - The Largest Clique(DAG+DP+SCC)

2024-07-15 23:05:01   223人阅读

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

强连通分量缩点+DAG的DP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
const int maxn = 1000+10;
const int maxm = 50000+10;
struct edge{
    int v,nxt;
}e[maxm];

int head[maxn];
int nume;
stack<int> S;
int dfs_clk;
int scc_no;
int dfn[maxn],lown[maxn],sccno[maxn];
int dp[maxn];
int n,m;
int num[maxn];
vector<int> G[maxn];
void init(){
    while(!S.empty()) S.pop();
    memset(head,0,sizeof head);
    memset(num,0,sizeof num);
    memset(dp,-1,sizeof dp);
    for(int i = 0; i <= n; i++){
        G[i].clear();
    }
    nume = 1;
    dfs_clk = 0;
    scc_no = 0;
    memset(dfn,0,sizeof dfn);
    memset(sccno,0,sizeof sccno);
}
void addedge(int u,int v){
    e[++nume].nxt = head[u];
    e[nume].v = v;
    head[u] = nume;
}

void dfs(int u){
    dfn[u] = lown[u] = ++dfs_clk;
    S.push(u);
    for(int i = head[u]; i ; i = e[i].nxt){
        int v = e[i].v;
        if(!dfn[v]){
            dfs(v);
            lown[u] = min(lown[u],lown[v]);
        }
        else if(!sccno[v]){
            lown[u] = min(lown[u],dfn[v]);
        }
    }
    if(lown[u] == dfn[u]){
        scc_no++;
        while(true){
            int x = S.top(); S.pop();
            sccno[x] = scc_no;
            if(x==u) break;
        }
    }
}

void find_scc(){
    for(int i = 1; i <= n; i++){
        if(!dfn[i])
            dfs(i);
    }
}

int dfs_dp(int x){
    if(dp[x] != -1) return dp[x];
    int ret = 0;
    for(int i = 0; i < G[x].size(); i++){
        int d = G[x][i];
        ret = max(ret,dfs_dp(d)+num[x]);
    }
    if(G[x].size()==0) ret = num[x];
    return dp[x] = ret;
}

void solve(){
    for(int i = 1; i <= n; i++){
        int d = sccno[i];
        num[d]++;
        for(int j = head[i]; j; j = e[j].nxt){
            if(d!=sccno[e[j].v])
                G[d].push_back(sccno[e[j].v]);
        }
    }
    int ret = 0;
    for(int i = 1; i <= scc_no; i++){
        ret = max(ret,dfs_dp(i));
    }
    printf("%d\n",ret);

}
int main(){

    int ncase;
    cin >> ncase;
    while(ncase--){
        scanf("%d%d",&n,&m);
        init();
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            addedge(a,b);
        }
        find_scc();
        solve();

    }
    return 0;
}



联系
我们