[UVA] 11324 - The Largest Clique

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define N 1005
vector<int> s[N];
vector<int> _s[N];
stack<int> _stack;
queue<int> _queue;
int pre[N],sccno[N],dfs_clock,scc_cnt;
int val[N],in[N],dp[N];
int dfs(int u,int fa){
    int lowu,lowv,i;
    lowu=pre[u]=++dfs_clock;
    _stack.push(u);
    for(i=0;i<s[u].size();i++){
        int v=s[u][i];
        if(!pre[v]){
            lowv=dfs(v,u);
            lowu=min(lowu,lowv);
        }
        else if(!sccno[v]){
            lowu=min(lowu,pre[v]);
        }
    }
    if(lowu==pre[u]){
        ++scc_cnt;
        while(1){
            int x=_stack.top();
            val[scc_cnt]++;
            _stack.pop();
            sccno[x]=scc_cnt;
            if(x==u) break;
        }
    }
    return lowu;
}
int main(){
    int t,n,m,x,y,i,j,A,B;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        memset(pre,0,sizeof(pre));
        memset(sccno,0,sizeof(sccno));
        memset(val,0,sizeof(val));
        memset(in,0,sizeof(in));
        memset(dp,0,sizeof(dp));
        A=B=scc_cnt=0;
        for(i=1;i<=n;i++)
            s[i].clear();
        for(i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            s[x].push_back(y);
        }
        for(i=1;i<=n;i++){
            dfs_clock=0;
            if(!pre[i]){
                dfs(i,-1);
            }
        }
        for(i=1;i<=scc_cnt;i++){
            _s[i].clear();
        }
        for(i=1;i<=n;i++){
            for(j=0;j<s[i].size();j++){
                int v=s[i][j];
                if(sccno[i]!=sccno[v]){
                    _s[sccno[i]].push_back(sccno[v]);
                    in[sccno[v]]++;
                }
            }
        }
        int ans=0;
        for(i=1;i<=scc_cnt;i++){
            dp[i]=val[i];
            if(in[i]==0){
                _queue.push(i);
            }
        }
        while(_queue.size()){
            int u=_queue.front();
            _queue.pop();
            for(i=0;i<_s[u].size();i++){
                int v=_s[u][i];
                if(dp[u]+val[v]>dp[v]){
                    dp[v]=dp[u]+val[v];
                    ans=max(ans,dp[v]);
                }
                in[v]--;
                if(in[v]==0)
                    _queue.push(v);
            }
        }
        for(i=1;i<=scc_cnt;i++)
            ans=max(ans,dp[i]);
        printf("%d\n",ans);
    }
}