UVAoj 11324 - The Largest Clique(tarjan + dp)

缩点要么选要么不选，问题就转换成了DAG图上的最长路径！

#include<iostream>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 1005
using namespace std;

struct EDGE{
    int u, v, nt;
    EDGE(){}
    EDGE(int u, int v, int nt) : u(u), v(v), nt(nt){}
};

int first[N];
vector<EDGE>g;
vector<EDGE>gg;
int scc_cnt, dfs_clock;
int scc[N];
int pre[N], low[N];
int dp[N], cnt[N];

int in[N];
int n, m;
stack<int>s;

void dfs(int u){
    pre[u] = low[u] = ++dfs_clock;
    s.push(u);
    for(int i = first[u]; ~i; i = g[i].nt){
        int v = g[i].v;
        if(!pre[v]){
            dfs(v);
            low[u] = min(low[u], low[v]);
        }else if(!scc[v])
            low[u] = min(low[u], pre[v]);
    }
    if(low[u] == pre[u]){
        ++scc_cnt;
        while(1){
            ++cnt[scc_cnt];
            int x = s.top(); s.pop();
            scc[x] = scc_cnt;
            if(x==u) break;
        }
    }
}

void addEdge(int u, int v){
    g.push_back(EDGE(u, v, first[u]));
    first[u] = g.size() - 1;
}

void tarjans(){
    memset(pre, 0, sizeof(pre));
    memset(scc, 0, sizeof(scc));
    memset(cnt, 0, sizeof(cnt));
    memset(dp, 0, sizeof(dp));
    memset(in, 0, sizeof(in));
    scc_cnt = 0;
    dfs_clock = 0;
    for(int i=1; i<=n; ++i)
        if(!pre[i]) dfs(i);
    int len = g.size();
    memset(first, -1, sizeof(first));
    gg.clear();
    for(int i=0; i<len; ++i)
        if(scc[g[i].u] != scc[g[i].v]){
             in[scc[g[i].v]]++;
             gg.push_back(EDGE(scc[g[i].u], scc[g[i].v], first[scc[g[i].u]]));
             first[scc[g[i].u]] = gg.size() - 1;
        }
    int maxN = 0;    
    queue<int>q;
    for(int i=1; i<=scc_cnt; ++i)
        if(!in[i]){
           dp[i] = cnt[i];
           q.push(i);
           if(maxN < dp[i]) maxN = dp[i];
        }
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i=first[u]; ~i; i = gg[i].nt){
            int v = gg[i].v;
            dp[v] = max(dp[v], dp[u] + cnt[v]);
            q.push(v);
            if(maxN < dp[v]) maxN = dp[v];
        }
    }
    printf("%d\n", maxN); 
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        memset(first, -1, sizeof(first));
        scanf("%d%d", &n, &m);
        while(m--){
            int u, v;
            scanf("%d%d", &u, &v);
            addEdge(u, v);
        }
        tarjans();    
        g.clear();
    }
    return 0;
}