题目
一个有向图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的余数。
输入格式
第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述接下来M行，每行两个正整
数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。N ≤1
00000, M ≤1000000；对于100%的数据， X ≤10^8
输出格式
应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.
输入样例
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
输出样例
3
3
题解
一开始被题目吓到了，仔细读题才知道原来就是一个tarjan缩点
最大半连通，其实就是诱导子图中，每对点至少能从其中一个到达另一个。
强联通分量里的点相互到达，缩点。
缩完后是一个DAG图，最大的所求图就是最长的路径了【只有同一条路径长的点满足要求】
要注意的就是统计时要防止由于缩点后新建的重边而重复计算，我用了一个vis数组表示当前点最后被哪个点访问过
具体看代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)
using namespace std;
const int maxn = 100005,maxm = 1000005,INF = 1000000000;
inline int RD(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57) {
if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}return out * flag;
}
int N,M,P,h[maxn],ne = 0,head[maxn],nedge = 0;
struct EDGE{
int to,nxt;}ed[maxm],edge[maxm];
inline void build(int u,int v){ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;}
inline void add(int u,int v){edge[nedge] = (EDGE){v,head[u]}; head[u] = nedge++;}
int Scc[maxn],scci = 0,st[maxn],top = 0,low[maxn],dfn[maxn],cnt = 0,Siz[maxn];
void dfs(int u){dfn[u] = low[u] = ++cnt;st[++top] = u; int to;Redge(u){if (!dfn[to = ed[k].to]) dfs(to);if (dfn[to] && !Scc[to]) low[u] = min(low[u],low[to]);}if (dfn[u] == low[u]){scci++;do {Scc[st[top]] = scci; Siz[scci]++;}while (st[top--] != u);}
}
void tarjan(){REP(i,N) if (!dfn[i]) dfs(i);}
queue<int> q;
int f[maxn],g[maxn],inde[maxn],vis[maxn];
void solve(){memset(head,-1,sizeof(head));int u,to;REP(i,N){u = Scc[i];Redge(i) if (Scc[to = ed[k].to] != u) add(u,Scc[to]),inde[Scc[to]]++;}REP(i,scci) if (!inde[i]) q.push(i),g[i] = 1;while (!q.empty()){u = q.front(); q.pop();f[u] += Siz[u];for (int k = head[u]; k != -1; k = edge[k].nxt){if (!(--inde[to = edge[k].to])) q.push(to);if (vis[to] != u){vis[to] = u;if (f[to] < f[u]) f[to] = f[u],g[to] = g[u];else if (f[to] == f[u]) g[to] = (g[to] + g[u]) % P;}}}int ans = 0,gmax = -1;REP(i,scci)if (f[i] > gmax) {ans = g[i]; gmax = f[i];}else if (f[i] == gmax) ans = (ans + g[i]) % P;printf("%d\n%d\n",gmax,ans);
}
int main(){memset(h,-1,sizeof(h));N = RD(); M = RD(); P = RD(); int a,b;while (M--) a = RD(),b = RD(),build(a,b);tarjan();solve();return 0;
}