The Largest Clique UVA 11324 （缩点后求DAG上最长路）

题意：给一个有向图G，求一个结点数最大的结点集。其中，要求里面任意的两点u,v.使得u能达到v，或者v能达到u，当然，u，v中互相可达也是可以的。 分析：选择一个强联通分量肯定是血赚不亏的，因为里面的点都是互相可达的。我们先进行缩点，得到一个DAG图，结点的权值是该联通分量里面点的数量。题目转化为在这个DAG上求最长路。 那么算法就很容易实现了，先Tarjan缩点，然后建立一个新的图，注意，可能会有重边，所以我们不能用邻接表处理，用一个邻接矩阵表示新图。在新图上求DAG上的最长路即可。 代码：

#include
using namespace std;
const int maxn = 1005;
const int maxm = 5e5+4;
vector G[maxn];
int pre[maxn],lowlink[maxn],sccnow[maxn],dfs_clock,scc_cnt;
int val[maxn];
stack S;
void dfs(int u){
	pre[u]=lowlink[u]= ++dfs_clock;
	S.push(u);
	for(int i=0;iT;
	while(T--){
		int n,m;scanf("%d%d",&n,&m);
		for(int i=0;i