。。。 错了很多次啊 细节问题啊。。
坑爹啊 两小时就这样没了
#include<cstdio> #include<cstring> #include<vector> #include<stack> #include<algorithm> using namespace std; const int MAXN = 1007; vector<int> G[MAXN], scc[MAXN], D[MAXN]; int pt[MAXN], low[MAXN], dt; int sccno[MAXN], sccn; stack<int> stk; bool inque[MAXN]; int d[MAXN]; int dfs(int u) { pt[u] = low[u] = ++dt; stk.push(u); int i, v, sz = G[u].size(); for(i = 0; i < sz; i++) { v = G[u][i]; if( !pt[v]) low[u] = min(low[u], dfs(v)); else if( !sccno[v]) low[u] = min(low[u], pt[v]); } if(low[u] == pt[u]) { sccn ++; scc[sccn].clear(); while( !stk.empty()) { v = stk.top(); stk.pop(); scc[sccn].push_back(v); sccno[v] = sccn; if(v == u) break; } } return low[u]; } void getscc(int n) { dt = sccn = 0; while( !stk.empty()) stk.pop(); memset(pt, 0, sizeof(pt)); memset(sccno, 0, sizeof(sccno)); for(int i = 1; i <= n; i++) if( !pt[i]) dfs(i); } int dp(int u) { if( d[u]) return d[u]; int ret = 0; for(int i = 0; i < D[u].size(); i++) ret = max(ret, dp(D[u][i])); return d[u] = ret + scc[u].size(); } int main() { int T, n, m, u, v, i, j; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); for(i = 1; i <= n; i++) G[i].clear(); for(i = 1; i <= m; i++) { scanf("%d%d", &u, &v); G[u].push_back(v); } getscc(n); for(i = 1; i <= sccn; i++) D[i].clear(); for(i = 1; i <= n; i ++) { int sz = G[i].size(); for(j = 0; j < sz; j++) { v = G[i][j]; if(sccno[i] == sccno[v]) continue; D[sccno[i]].push_back(sccno[v]); } } int ans = 0; memset(d, 0, sizeof(d)); for(i = 1; i <= sccn; i++) ans = max(ans, dp(i)); printf("%d\n", ans); } return 0; }