My 4th purple problem.

难度： 紫

算法： 强连通分量相关，拓扑排序

先跑一遍强连通分量，然后缩点。注意去除重边。

显然，那个最大半连通子图就是然后对缩完点的图进行拓扑排序，按照拓扑排序进行搜索，更新搜到的点即可。

本题码量较大，搜索部分的实现难度较高，自己打不出来可以看代码。

时间复杂度 $O(mlogm)$ 因为要去重边。

注意： 不要把拓扑排序写成纯搜索。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,x,a,b,te;
int l[100100],d[100100],in[100100],s[100100],c,t,sz[100100],f[100100],g[100100],mans,ans,pt[100100];
stack<int> st;
priority_queue<int,vector<int>,greater<int> > q[100100];
vector<int> e[100100],k[100100];
queue<int> tpo,r;
void tarj(int u){
	l[u]=d[u]=++c;
	st.push(u);
	in[u]=1;
	for(int i=0;i<int(e[u].size());i++){
		int v=e[u][i];
		if(!d[v]){
			tarj(v);
			l[u]=min(l[u],l[v]);
		}
		else if(in[v]){
			l[u]=min(l[u],d[v]);
		}
	}
	if(l[u]==d[u]){
		++t;
		while(1){
			s[st.top()]=t;
			in[st.top()]=0;
			if(st.top()==u){
				st.pop();
				break;
			}
			st.pop();
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&x);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
	}
	for(int i=1;i<=n;i++){
		if(!d[i]) tarj(i);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<int(e[i].size());j++){
			if(s[i]!=s[e[i][j]]) q[s[i]].push(s[e[i][j]]);
		} 
	}
	for(int i=1;i<=n;i++){
		sz[s[i]]++;
	}
	n=t;
	for(int i=1;i<=n;i++){
		while(!q[i].empty()){
			te=q[i].top();
			k[i].push_back(te);
			pt[te]++;
			while(!q[i].empty()){
				if(q[i].top()==te) q[i].pop();
				else break;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(pt[i]==0) tpo.push(i),f[i]=sz[i],mans=max(mans,f[i]),g[i]=1;
	}
	while(!tpo.empty()){
		int u=tpo.front();
		tpo.pop();
		for(int i=0;i<int(k[u].size());i++){
			int v=k[u][i];
			pt[v]--;
			if(pt[v]==0) tpo.push(v);
			if(f[v]<f[u]+sz[v]){
				f[v]=f[u]+sz[v];
				g[v]=g[u]%x; 
			} 
			else if(f[v]==f[u]+sz[v]){
				g[v]=(g[v]+g[u])%x;
			}
			mans=max(mans,f[v]);
		}
	}
	for(int i=1;i<=n;i++){
		if(f[i]==mans) ans=(ans+g[i])%x;
	}
	printf("%d\n%d",mans,ans);
	return 0;
}