UVA 11324 The Largest Clique

。。。 错了很多次啊 细节问题啊。。

坑爹啊 两小时就这样没了

#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;
}