这道题很迷，为什么呢？因为题面的封面很迷。

题目描述

给你一张有向图 G，求一个结点数最大的结点集，使得该结点集中的任意两个结点 u 和 v 满足：要么 u 可以达 v，要么 v 可以达 u（u,v相互可达也行）。

原题链接

Slove

其实这个题就是个裸题，适宜初学tarjan的练习。
强连通分量（tarjan）+缩点+DAG，DP。

1. tarjan强连通分量缩点。
2. DAG上跑DP。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#define N 500001
using namespace std;  //标准开头
int t;
int n,m;  //t，n，m同题
int u,v;  //同题
int x[N],y[N];  //数组存边
int dis[N];  //dis[i]-从强连通分量节点为i最多能到节点数
int st[N],num;  //st-栈
int dfn[N],low[N],sz[N],cnt,sum;
int first1[N],first2[N],nxt1[N],nxt2[N],to1[N],to2[N],len1,len2,fis[N];  //邻接表
//fis[i]-节点i所在的强连通分量编号
bool vis[N]; //是否在栈中
bool mis[N];  //缩点后的点，是否有前驱
void add1(int u,int v){
   to1[++len1]=v;
   nxt1[len1]=first1[u];
   first1[u]=len1;
}
void add2(int u,int v){  //缩点邻接表
   to2[++len2]=v;
   nxt2[len2]=first2[u];
   first2[u]=len2;
}
void tarjan(int s){
   dfn[s]=low[s]=++sum;
   st[++num]=s;
   vis[s]=true;
   for(int i=first1[s];i!=-1;i=nxt1[i]){
   	if(!dfn[to1[i]]){
   		tarjan(to1[i]);
   		low[s]=min(low[s],low[to1[i]]);
   	}
   	else if(vis[to1[i]]) low[s]=min(low[s],dfn[to1[i]]);
   }
   if(dfn[s]==low[s]){
   	int cur;
   	cnt++;
   	do{
   		cur=st[num];
   		sz[cnt]++;
   		vis[cur]=false;
   		fis[cur]=cnt;
   		num--;
   	}while(cur!=s);
   }
}
int dp(int s){
   if(dis[s]) return dis[s];
   dis[s]+=sz[s];
   int ans=0;
   for(int i=first2[s];i!=-1;i=nxt2[i]) ans=max(ans,dp(to2[i]));
   dis[s]+=ans;
   return dis[s];
}
int main()
{
   scanf("%d",&t);
   while(t--){
   	len1=len2=num=cnt=sum=0;
   	scanf("%d%d",&n,&m);
   	for(int i=1;i<=n;i++){
   		dfn[i]=low[i]=sz[i]=dis[i]=0;
   		first1[i]=first2[i]=-1;
   		vis[i]=false;
   		mis[i]=false;
   		st[i]=0;
   	}
   	for(int i=1;i<=m;i++){
   		scanf("%d%d",&u,&v);
   		add1(u,v);
   		x[i]=u;
   		y[i]=v;
   	}
   	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
   	for(int i=1;i<=m;i++){
   		if(fis[x[i]]!=fis[y[i]]) add2(fis[x[i]],fis[y[i]]),mis[fis[y[i]]]=true;
   	}
   	int maxn=0;
   	for(int i=1;i<=cnt;i++) if(!mis[i]) dp(i),maxn=max(maxn,dis[i]);
   	printf("%d\n",maxn);
   }
   return 0;
}