学步园

链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=25&problem=2299&mosmsg=Submission+received+with+ID+14404690

题意：一个有向图，找一个最大的点集使得任意两点u、v间都存在一条路（单向或双向），问这个点集最大是多少

思路：强连通分量缩点后得到SCC图，使SCC结点的权等于它的节点个数，找一条路径使得权值和最大即可，找路径用dp记忆化搜索

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 1010
#define eps 1e-7
#define INF 0x3F3F3F3F      //0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 1313131
#define MOD 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int maxm = 50010;
struct node{
    int u, v, next;
}edge[maxm], edge1[maxm];
int Stack[MAXN];
int head[MAXN], head1[MAXN], dfn[MAXN], low[MAXN], sccno[MAXN], scc_elem[MAXN];
int scc_cnt, id, cnt, cnt1, top, n, m;
int dp[MAXN];
void add_edge(int u, int v, node edge[], int head[], int &cnt){
    edge[cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void tarjin(int u){
    int i, j;
    dfn[u] = low[u] = ++id;
    Stack[top++] = u;
    for(i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].v;
        if(dfn[v] == -1){
            tarjin(v);
            low[u] = min(low[u], low[v]);
        }
        else if(!sccno[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]){
        scc_cnt++;
        int temp;
        do{
            temp = Stack[--top];
            sccno[temp] = scc_cnt;
        }while(temp != u);
    }
}
int dfs_DAG(int u){
    if(dp[u] > 0)   return dp[u];
    dp[u] = scc_elem[u];
    for(int i = head1[u]; i != -1; i = edge1[i].next){
        int v = edge1[i].v;
        dp[u] = max(dp[u], scc_elem[u] + dfs_DAG(v));
    }
    return dp[u];
}
int main(){
    int i, j, t;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        cnt = cnt1 = scc_cnt = id = top = 0;
        memset(head, -1, sizeof(head));
        memset(head1, -1, sizeof(head1));
        memset(dfn, -1, sizeof(dfn));
        memset(sccno, 0, sizeof(sccno));
        memset(scc_elem, 0, sizeof(scc_elem));
        for(i = 0; i < m; i++){
            int u, v;
            scanf("%d%d", &u, &v);
            add_edge(u, v, edge, head, cnt);
        }
        for(i = 1; i <= n; i++){
            if(dfn[i] == -1)    tarjin(i);
        }
        for(i = 1; i <= n; i++){
            int x = sccno[i];
            scc_elem[x]++;
        }
        for(i = 0; i < cnt; i++){
            int u = edge[i].u;
            int v = edge[i].v;
            if(sccno[u] != sccno[v]){
                add_edge(sccno[u], sccno[v], edge1, head1, cnt1);
            }
        }
        memset(dp, 0, sizeof(dp));
        int ans = 0;
        for(i = 1; i <= scc_cnt; i++){
            ans = max(ans, dfs_DAG(i));
        }
        printf("%d\n", ans);
    }
    return 0;
}