题意：
给一张有向图G，求一个结点数最大的结点集，使得该结点中任意两个结点 u 和 v满足：要么 u 可以到达 v， 要么 v 可以到达 u（u 和 v 相互可达也可以）。
分析：
Tarjan求SCC缩点，SCC的节点数为新点点权，然后求DAG上权最大的的路径。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define Maxn 1010
#define Maxm 50010 struct node
{
int x,y,next;
}t[Maxm]; int first[Maxn],dfn[Maxn],low[Maxn],sta[Maxn],scc[Maxn],sum[Maxn];
bool bj[Maxn],bj2[Maxn],map[Maxn][Maxn];
int cnt,sl,cl; int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} void ffind(int x)
{
dfn[x]=low[x]=++cnt;
sta[++sl]=x;
for(int i=first[x];i;i=t[i].next)
{
int y=t[i].y;
if(dfn[y]==)
{
ffind(y);
low[x]=mymin(low[x],low[y]);
}
else if(scc[y]==) low[x]=mymin(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
cl++;
while()
{
int z=sta[sl--];
scc[z]=cl;
sum[cl]++;
if(z==x) break;
}
}
} int dfs(int x)
{
int ans=;
bj[x]=;
for(int i=;i<=cl;i++) if(map[x][i]==&&bj[i]==)
ans=mymax(ans,dfs(i));
ans+=sum[x];
bj[x]=;
return ans;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m,ans=;
scanf("%d%d",&n,&m);
memset(first,,sizeof(first));
memset(dfn,,sizeof(dfn));
memset(sum,,sizeof(sum));
memset(bj,,sizeof(bj));
memset(map,,sizeof(map));
memset(scc,,sizeof(scc));
cnt=;sl=;cl=;
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&t[i].x,&t[i].y);
t[i].next=first[t[i].x];first[t[i].x]=i;
}
for(int i=;i<=n;i++) if(dfn[i]==) ffind(i);
for(int i=;i<=m;i++) if(scc[t[i].x]!=scc[t[i].y]) map[scc[t[i].x]][scc[t[i].y]]=;
for(int i=;i<=cl;i++) ans=mymax(ans,dfs(i));
printf("%d\n",ans);
}
return ;
}
UVA11324
2016-03-17 16:54:20