| UVA - 11324 |
题意：求一个节点数最大的节点集，使任意两个节点至少从一个可以到另一个
同一个SCC要选一定全选
求SCC 缩点建一个新图得到一个DAG，直接DP行了
这个新图不需要判重边，重边就是真实存在
//
// main.cpp
// 最大团
//
// Created by Candy on 02/11/2016.
// Copyright © 2016 Candy. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define C(x) memset(x,0,sizeof(x))
using namespace std;
const int N=1e3+,M=5e4+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int T,n,m,u,v;
struct edge{
int v,ne;
}e[M];
int h[N],cnt=;
inline void ins(int u,int v){
cnt++;
e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
}
int dfn[N],low[N],belong[N],dfc,scc,size[N];
int st[N],top;
void dfs(int u){
dfn[u]=low[u]=++dfc;
st[++top]=u;
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}else if(!belong[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
scc++;
while(true){
int x=st[top--];
belong[x]=scc;
size[scc]++;
if(x==u) break;
}
}
}
void SCC(){
dfc=scc=;
C(dfn);C(low);C(belong);C(size);
top=;
for(int i=;i<=n;i++) if(!dfn[i]) dfs(i);
} edge es[N];
int hs[N],cs=;
inline void inss(int u,int v){
cs++;
es[cs].v=v;es[cs].ne=hs[u];hs[u]=cs;
}
void buildGraph(){
cs=;
C(hs);
for(int u=;u<=n;u++){
int a=belong[u];
for(int i=h[u];i;i=e[i].ne){
int b=belong[e[i].v];
if(a!=b) inss(a,b);
}
}
}
int f[N];
int dp(int u){
if(f[u]!=-) return f[u];
f[u]=size[u];
int mx=;
for(int i=hs[u];i;i=es[i].ne){
int v=es[i].v;//printf("dp %d v %d\n",u,v);
mx=max(mx,dp(v));
}
return f[u]+=mx;
}
int main(int argc, const char * argv[]) {
T=read();
while(T--){
n=read();m=read();
cnt=;memset(h,,sizeof(h));
for(int i=;i<=m;i++){u=read();v=read();ins(u,v);}
SCC();
buildGraph(); memset(f,-,sizeof(f));
int ans=;
for(int i=;i<=scc;i++){
if(f[i]==-) dp(i);
ans=max(ans,f[i]);
}
printf("%d\n",ans);
} return ;
}