最大团，
problem:给一个有向图G， 求一个节点数最大的点集， 使得该点集中的任意两个节点至少要有一条路径
->
那么可知， G中的SCC要么都选， 要么都不选（不选是因为这是有向图选了之后的无法纳入范围）， 那么问题就简单了
将每个SCC缩成一个点， 变成在DAG上DP
->
code:
#include#include #include #include using namespace std;#define N 50005#define next Next#define begin Begin#define mem(a) memset(a, 0, sizeof(a))#define rep(i, j, k) for(int i=j; i<=k; ++i)#define erep(i, u) for(int i=begin[u]; i; i=next[i])void read(int &x){ char c=getchar();x=0;while(c<'0' || c>'9')c=getchar(); while(c>='0' && c<='9')x=x*10+c-'0', c=getchar();}int begin[N<<1], to[N<<1], next[N<<1], e;void add(int x, int y){ to[++e]=y; next[e]=begin[x]; begin[x]=e;}int n, m, low[N], pre[N], sccid[N], scc_cnt, clock_;stack s;void dfs(int u){ pre[u]=low[u]=++clock_; s.push(u); erep(i, u){ int v=to[i]; if(!pre[v])dfs(v),low[u]=min(low[u], low[v]); else if(!sccid[v])low[u]=min(low[u], pre[v]); //notice! array low can only reach the point which is in the same SCC; } if(pre[u] == low[u]){ scc_cnt++; while(1){ int x=s.top();s.pop(); sccid[x]=scc_cnt;if(x == u)break; } }}void solve(){ clock_ = scc_cnt = 0; mem(pre);mem(sccid); rep(i, 1, n) if(!pre[i]) dfs(i);}int f[1005], w[1005];bool p[1005],vis[1005][1005];int dp(int u){ if(f[u]>=0)return f[u]; f[u]=w[u]; rep(v, 1, scc_cnt) if(v!=u && vis[u][v])f[u]=max(f[u], w[u]+dp(v)); return f[u];}int main(){#ifndef ONLINE_JUDGE freopen("data.in", "r", stdin); freopen("result.out", "w", stdout);#endif int _; read(_); while(_--){ e=0; mem(begin); memset(f, -1, sizeof(f)); mem(vis);mem(w); read(n);read(m); rep(i, 1, m){ int u, v; read(u);read(v); add(u, v); } solve(); rep(i, 1, n){ w[sccid[i]]++; erep(j, i) vis[sccid[i]][sccid[to[j]]]=true; } int res=0; rep(i, 1, scc_cnt) res=max(res, dp(i)); printf("%d\n", res); } return 0;}