题意：给定一个有向图，寻找一个点数最大集合，使得这个集合中的任意两个点

u,v, 都有u->v 或者 v->u 或者u<==>v

思路：首先将强连通分量通过tarjan算法求出来，然后进行缩点，也就是每一个缩点

所组成的图就是一个DAG图！令每一个点的权值就是这个缩点所包含节点（也就是对应的

强连通分量的节点数目），因为强连通分量的任意的两个节点都是相互可达的，那么这个

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

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #define N 1005 9 using namespace std; 10 11 struct EDGE{ 12 int u, v, nt; 13 EDGE(){} 14 EDGE(int u, int v, int nt) : u(u), v(v), nt(nt){} 15 }; 16 17 int first[N]; 18 vector
             
              g; 19 vector
              
               gg; 20 int scc_cnt, dfs_clock; 21 int scc[N]; 22 int pre[N], low[N]; 23 int dp[N], cnt[N]; 24 25 int in[N]; 26 int n, m; 27 stack
               
                s; 28 29 void dfs(int u){ 30 pre[u] = low[u] = ++dfs_clock; 31 s.push(u); 32 for(int i = first[u]; ~i; i = g[i].nt){ 33 int v = g[i].v; 34 if(!pre[v]){ 35 dfs(v); 36 low[u] = min(low[u], low[v]); 37 }else if(!scc[v]) 38 low[u] = min(low[u], pre[v]); 39 } 40 if(low[u] == pre[u]){ 41 ++scc_cnt; 42 while(1){ 43 ++cnt[scc_cnt]; 44 int x = s.top(); s.pop(); 45 scc[x] = scc_cnt; 46 if(x==u) break; 47 } 48 } 49 } 50 51 void addEdge(int u, int v){ 52 g.push_back(EDGE(u, v, first[u])); 53 first[u] = g.size() - 1; 54 } 55 56 void tarjans(){ 57 memset(pre, 0, sizeof(pre)); 58 memset(scc, 0, sizeof(scc)); 59 memset(cnt, 0, sizeof(cnt)); 60 memset(dp, 0, sizeof(dp)); 61 memset(in, 0, sizeof(in)); 62 scc_cnt = 0; 63 dfs_clock = 0; 64 for(int i=1; i<=n; ++i) 65 if(!pre[i]) dfs(i); 66 int len = g.size(); 67 memset(first, -1, sizeof(first)); 68 gg.clear(); 69 for(int i=0; i
                

q; 77 for(int i=1; i<=scc_cnt; ++i) 78 if(!in[i]){ 79 dp[i] = cnt[i]; 80 q.push(i); 81 if(maxN < dp[i]) maxN = dp[i]; 82 } 83 while(!q.empty()){ 84 int u = q.front(); q.pop(); 85 for(int i=first[u]; ~i; i = gg[i].nt){ 86 int v = gg[i].v; 87 dp[v] = max(dp[v], dp[u] + cnt[v]); 88 q.push(v); 89 if(maxN < dp[v]) maxN = dp[v]; 90 } 91 } 92 printf("%d\n", maxN); 93 } 94 95 int main(){ 96 int t; 97 scanf("%d", &t); 98 while(t--){ 99 memset(first, -1, sizeof(first));100 scanf("%d%d", &n, &m);101 while(m--){102 int u, v;103 scanf("%d%d", &u, &v);104 addEdge(u, v);105 }106 tarjans(); 107 g.clear();108 }109 return 0;110 }