题目：
题意：
给你一个有向图，求一个点集合的最大大小，使得此点集合中对于任意点对(u,v)，有从u到v或者从v到u的边
方法：
先找强连通分量缩点，每个强连通分量显然满足条件，然后在缩点后的图中找到一条权值最大的路径，权值为此路径的点权之和，点权为这个强连通分量的点数
1 int dp[maxn]; 2 int dfs(int u) 3 { 4 if (dp[u]) return dp[u]; 5 int ret = 0; 6 for (int i = head[u]; ~i; i = edge[i].next) 7 ret = max(ret, dfs(edge[i].v)); 8 return dp[u] = ret + node[u]; 9 }
代码：
1 /******************************************** 2 *ACM Solutions 3 * 4 *@Title: 5 *@Version: 1.0 6 *@Time: 2014-xx-xx 7 *@Solution: http://www.cnblogs.com/xysmlx/p/xxxxxxx.html 8 * 9 *@Author: xysmlx(Lingxiao Ma) 10 *@Blog: http://www.cnblogs.com/xysmlx 11 *@EMail: xysmlx@163.com 12 * 13 *Copyright (C) 2011-2015 xysmlx(Lingxiao Ma) 14 ********************************************/ 15 // #pragma comment(linker, "/STACK:102400000,102400000") 16 #include <cstdio> 17 #include <iostream> 18 #include <cstring> 19 #include <string> 20 #include <cmath> 21 #include <set> 22 #include <list> 23 #include <map> 24 #include <iterator> 25 #include <cstdlib> 26 #include <vector> 27 #include <queue> 28 #include <ctime> 29 #include <stack> 30 #include <algorithm> 31 #include <functional> 32 using namespace std; 33 typedef long long ll; 34 #define pb push_back 35 #define ROUND(x) round(x) 36 #define FLOOR(x) floor(x) 37 #define CEIL(x) ceil(x) 38 const int maxn = 1010; 39 const int maxm = 200010; 40 const int inf = 0x3f3f3f3f; 41 const ll inf64 = 0x3f3f3f3f3f3f3f3fLL; 42 const double INF = 1e30; 43 const double eps = 1e-6; 44 int kase; 45 int n, m; 46 struct Edge 47 { 48 int u, v; 49 int next; 50 Edge(int _u, int _v, int _next): u(_u), v(_v), next(_next) {} 51 Edge() {} 52 } edge[maxm]; 53 int en; 54 int head[maxn]; 55 int node[maxn]; 56 void addse(int u, int v) 57 { 58 edge[en] = Edge(u, v, head[u]); 59 head[u] = en++; 60 } 61 struct SCC 62 { 63 Edge edge[maxm]; 64 int en; 65 int head[maxn]; 66 int h[maxn]; 67 void addse(int u, int v) 68 { 69 edge[en] = Edge(u, v, head[u]); 70 head[u] = en++; 71 } 72 void init() 73 { 74 memset(head, -1, sizeof(head)); 75 en = 0; 76 } 77 int sid[maxn]; 78 int mark[maxn], low[maxn]; 79 int check[maxn]; 80 int sstack[maxn], top; 81 int dfn, ssn; 82 int n, m; 83 bool mtx[maxn][maxn]; 84 void dfs(int k) 85 { 86 int i, j; 87 check[k] = 1; 88 low[k] = mark[k] = dfn++; 89 sstack[top++] = k; 90 for (int i = head[k]; i != -1; i = edge[i].next) 91 { 92 int j = edge[i].v; 93 if (mark[j] == 0) 94 { 95 dfs(j); 96 low[k] = min(low[k], low[j]); 97 } 98 else if (check[j]) 99 low[k] = min(low[k], mark[j]); 100 } 101 if (mark[k] == low[k]) 102 { 103 while (sstack[--top] != k) 104 { 105 check[sstack[top]] = 0; 106 sid[sstack[top]] = ssn; 107 } 108 sid[k] = ssn; 109 check[k] = 0; 110 ++ssn; 111 } 112 return; 113 } 114 void tarjan() 115 { 116 ssn = 1; 117 dfn = 1; 118 top = 0; 119 memset(check, 0, sizeof(check)); 120 memset(mark, 0, sizeof(mark)); 121 for (int i = 0; i < n; ++i) if (mark[i] == 0) dfs(i); 122 123 memset(h, 0, sizeof(h)); 124 for (int i = 0; i < n; i++) 125 h[sid[i]]++; 126 memset(mtx, 0, sizeof(mtx)); 127 for (int i = 0; i < en; i++) 128 mtx[sid[edge[i].u]][sid[edge[i].v]] = 1; 129 } 130 } scc; 131 132 int dp[maxn]; 133 int dfs(int u) 134 { 135 if (dp[u]) return dp[u]; 136 int ret = 0; 137 for (int i = head[u]; ~i; i = edge[i].next) 138 ret = max(ret, dfs(edge[i].v)); 139 return dp[u] = ret + node[u]; 140 } 141 142 void init() 143 { 144 kase++; 145 scc.init(); 146 memset(head, -1, sizeof(head)); 147 en = 0; 148 memset(dp, 0, sizeof(dp)); 149 } 150 void input() 151 { 152 scanf("%d%d", &n, &m); 153 scc.n = n; 154 for (int i = 0; i < m; i++) 155 { 156 int u, v; 157 scanf("%d%d", &u, &v); 158 u--, v--; 159 scc.addse(u, v); 160 } 161 } 162 void debug() 163 { 164 // 165 } 166 void solve() 167 { 168 scc.tarjan(); 169 n = scc.ssn; 170 for (int i = 1; i < scc.ssn; i++) 171 { 172 for (int j = 1; j < scc.ssn; j++) 173 { 174 if (i == j) continue; 175 if (scc.mtx[i][j]) 176 addse(i, j); 177 } 178 } 179 for (int i = 1; i < scc.ssn; i++) 180 node[i] = scc.h[i]; 181 // for (int i = 1; i < scc.ssn; i++) 182 // cout << node[i] << " "; 183 // cout << endl; 184 int ans = 0; 185 memset(dp, 0, sizeof(dp)); 186 for (int i = 1; i < n; i++) 187 { 188 ans = max(ans, dfs(i)); 189 } 190 printf("%d ", ans); 191 } 192 void output() 193 { 194 // 195 } 196 int main() 197 { 198 // 32-bit 199 // int size = 256 << 20; // 256MB 200 // char *p = (char *)malloc(size) + size; 201 // __asm__("movl %0, %%esp " :: "r"(p)); 202 203 // 64-bit 204 // int size = 256 << 20; // 256MB 205 // char *p = (char *)malloc(size) + size; 206 // __asm__("movq %0, %%rsp " :: "r"(p)); 207 208 // std::ios_base::sync_with_stdio(false); 209 #ifdef xysmlx 210 freopen("in.txt", "r", stdin); 211 #endif 212 213 kase = 0; 214 int T; 215 scanf("%d", &T); 216 while (T--) 217 { 218 init(); 219 input(); 220 solve(); 221 output(); 222 } 223 return 0; 224 }