题目：The Largest Clique
题意：
给出一个有向图G，求一个所含节点数最大的子图，满足其种任意两个节点之间都存在一条路径，使这两个节点单向连通。
思路：
由于每个强连通分量一定符合条件，所以可以先tarjan缩点。
缩点后原图边成一个带权有向无环图（权值为这个新图中的节点代表的原图中点的个数），要求解图中的最长路，用dp即可。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 1000
#define maxm 5000int n,m;vector<int> a[maxn+5];int pre[maxn+5],low[maxn+5];
int clk;int scc[maxn+5];
int c[maxn+5];
int cnt;stack<int> s;int g[maxn+5][maxn+5];
int g_[maxn+5][maxn+5];vector<int> od;int f[maxn+5];void init() { //初始化for(int i=1; i<=maxn; i++) a[i].clear();memset(pre,0,sizeof(pre));memset(scc,0,sizeof(scc));memset(g,0,sizeof(g));memset(f,0,sizeof(f));memset(c,0,sizeof(c));clk=cnt=0;stack<int> emp;s=emp;od.clear();
}void readin() { //读入scanf("%d%d",&n,&m);for(int i=1; i<=m; i++) {int x,y;scanf("%d%d",&x,&y);a[x].push_back(y);}
}void tj(int u) { //tarjanpre[u]=low[u]=++clk;s.push(u);for(int i=0; i<a[u].size(); i++) {int v=a[u][i];if(!pre[v]) {tj(v);low[u]=min(low[v],low[u]);} else if(!scc[v]) {low[u]=min(pre[v],low[u]);}}if(low[u]==pre[u]) {int x;cnt++;do {x=s.top(),s.pop();scc[x]=cnt;c[cnt]++;} while(x!=u);}
}void make_g() { //缩点for(int i=1; i<=n; i++) {for(int j=0; j<a[i].size(); j++) {int u=scc[i],v=scc[a[i][j]];if(u!=v&&!g[u][v]) {g[u][v]=true;g[0][v]++;}}}
}void toposort() { //拓扑排序memcpy(g_,g,sizeof(g));int b[maxn+5]= {0};while(true) {vector<int> td;for(int i=1; i<=cnt; i++) {if(!g[0][i]&&!b[i]) {td.push_back(i);b[i]=true;}}if(!td.size()) break;for(int i=0; i<td.size(); i++) {int x=td[i];od.push_back(x);for(int j=1; j<=cnt; j++) {if(g[x][j]) {g[0][j]--;g[x][j]=0;}}}}memcpy(g,g_,sizeof(g_));
}int dp() { //动态规划for(int i=0; i<od.size(); i++) {int x=od[i];for(int j=1; j<=cnt; j++) {if(g[j][x]) {f[x]=max(f[x],f[j]+c[j]);}}}int s=0;for(int i=1; i<=cnt; i++) {s=max(s,f[i]+c[i]);}return s;
}int main() {int T;scanf("%d",&T);while(T--) {init();readin();for(int i=1; i<=n; i++) if(!pre[i]) tj(i);make_g();toposort();printf("%d\n",dp());}return 0;
}