题目描述： 一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：?u,v∈V，满足u→v或v→u，即对于图中任意两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。若G'=(V',E')满足V'?V，E'是E中所有跟V'有关的边，则称G'是G的一个导出子图。若G'是G的导出子图，且G'半连通，则称G'为G的半连通子图。若G'是G所有半连通子图中包含节点数最多的，则称G'是G的最大半连通子图。给定一个有向图G，请求出G的最大半连通子图拥有的节点数K，以及不同的最大半连通子图的数目C。由于C可能比较大，仅要求输出C对X的余数。
题解：拿到题目是懵的，这个题目要我做什么玩意？？后来去翻了翻演算法，导出子图的意思就是拿出一些点，并且保留这些点之间所有的边，然后我就明白了，这题就是要Tarjan缩完点之后，找出拥有最多点的路径，并且求出有几条这样的路径。好了，Tarjan已经打到很熟练了，而且还是这种缩点的Tarjan。问题就转化成了如何找出拥有最多节点的路径，以及这种路径的数量。百度之后发现有个东西叫拓扑序dp？？我是谁？我怎么从来没有听说过？行吧，那就学吧，发现就是一个很简单的dp，一边做拓扑序的时候一边把dp做了，说是dp，其实更像是一个递推，过程挺好理解的，写起来难度也不大。
坑点：我个人觉得这题的数据有点奇怪，因为我自己打的代码是没有if used[v] == cur then continue 以及 used[v] = cur。因为我想到，既然缩点了，而且rebuild过程也是符合我的直观判断，及不会出现重边，但是这样交上去WA了，于是乎我百度到了别人的AC代码，就差了这个部分，可以说是很难受了，题目是下午A的，但是到现在也没有思路为啥要多个used，希望如果哪位看官看出了问题所在，能够告知一下我。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
const int M = 1e6 + 16;
const int N = 1e5 + 16;
struct Edge
{
int u, v, nxt;
};
Edge edge[M];
int low[N], dfn[N], sta[N], col[N];
bool vis[N];
int dep, top, sum;
vector<int> son[N];
int n, m, X;
int head[N], ecnt;
void _add( int u, int v )
{
edge[ecnt].u = u;
edge[ecnt].v = v;
edge[ecnt].nxt = head[u];
head[u] = ecnt ++;
}
void tarjan( int u )
{
low[u] = dfn[u] = ++dep;
sta[++top] = u;
vis[u] = 1;
for ( int i = head[u]; i+1; i = edge[i].nxt )
{
int v = edge[i].v;
if ( !dfn[v] )
{
tarjan(v);
low[u] = min( low[u], low[v] );
}
else if ( vis[v] )
low[u] = min( low[u], low[v] );
}
if ( dfn[u] == low[u] )
{
col[u] = ++sum;
vis[u] = 0;
while ( sta[top] != u )
{
col[sta[top]] = sum;
vis[sta[top--]] = 0;
}
top --;
}
}
int in[N];
void rebuild()
{
for ( int i = 1; i <= n; i ++ )
{
for ( int j = head[i]; j+1; j = edge[j].nxt )
{
int v = edge[j].v;
if ( col[v] != col[i] )
{
son[col[i]].push_back(col[v]);
in[col[v]] ++;
}
}
}
}
void init()
{
ecnt = top = sum = dep = 0;
clr(head,-1);
clr(dfn,0);
clr(sta,0);
clr(col,0);
clr(vis,0);
for ( int i = 0; i <= n; i ++ )
son[i].clear();
}
int f[N], g[N];
int val[N];
int used[N];
void tp()
{
queue<int> q;
for ( int i = 1; i <= sum; i ++ )
{
if ( in[i] == 0 )
q.push(i);
f[i] = val[i], g[i] = 1;
}
while ( !q.empty() )
{
int cur = q.front(); q.pop();
for ( int i = 0; i < son[cur].size(); i ++ )
{
int v = son[cur][i];
in[v] --;
if ( in[v] == 0 )
q.push(v);
if ( used[v] == cur ) continue;
if ( f[cur] + val[v] > f[v] )
{
f[v] = f[cur] + val[v];
g[v] = g[cur];
}
else if ( f[cur] + val[v] == f[v] )
g[v] = ( g[v] + g[cur] ) % X;
used[v] = cur;
}
}
}
int main()
{
init();
scanf("%d%d%d", &n, &m, &X );
for ( int i = 0; i < m; i ++ )
{
int u, v;
scanf("%d%d", &u, &v);
_add(u,v);
}
for ( int i = 1; i <= n; i ++ )
if ( !dfn[i] )
tarjan(i);
rebuild();
for ( int i = 1; i <= n; i ++ )
val[col[i]] ++;
tp();
int ans1, ans2;
ans1 = ans2 = 0;
for ( int i = 1; i <= sum; i ++ )
{
if ( f[i] > ans1 )
ans1 = f[i], ans2 = g[i];
else if ( f[i] == ans1 )
ans2 = ( ans2 + g[i] ) % X;
}
printf("%d
%d
", ans1, ans2);
return 0;
}