1093 - [ZJOI2007]最大半连通子图

tarjan缩点+dp模板（题解bymod998244353）

记得处理缩点时的重边。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005,M=1000006;
struct Edge{
	int v,next;
}edge[M];
bool vis[N];
queue<int>q;
int n,low[N],mod,dfn[N],tcnt,pcnt,grp[N],dp[N],rd[N],sta[N],top,d[M][2],f[N],ecnt,m,siz[N],head[N];
map<pair<int,int>,bool>Map;
void addedge(int u,int v) {
	edge[++ecnt].v=v;
	edge[ecnt].next=head[u];
	head[u]=ecnt;
}
void tarjan(int u) {
	dfn[u]=low[u]=++tcnt;
	sta[++top]=u,vis[u]=true;
	for(int i=head[u],v; i; i=edge[i].next) {
		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],dfn[v]);
		}
	}
	if(low[u]==dfn[u]) {
		++pcnt;
		do {
			vis[sta[top]]=false;
			grp[sta[top]]=pcnt;
			++siz[pcnt];
		}while(sta[top--]^u);
	}
}
int main() {
	scanf("%d%d%d",&n,&m,&mod);
	for(int i=1,u,v; i<=m; ++i) {
		scanf("%d%d",&u,&v);
		d[i][0]=u,d[i][1]=v;
		addedge(u,v);
	}
	for(int i=1; i<=n; ++i)
		if(!dfn[i]) {
			tarjan(i);
		}
	ecnt=0,memset(head,0,sizeof(head));
	for(int i=1,u,v; i<=m; ++i) {
		u=d[i][0],v=d[i][1];
		if(grp[u]!=grp[v]&&!Map[make_pair(grp[u],grp[v])]) {
			Map[make_pair(grp[u],grp[v])]=1;
			addedge(grp[u],grp[v]);
			++rd[grp[v]];
		}
	}
	for(int i=1; i<=pcnt; ++i)
		if(!rd[i]) {
			q.push(i);
			dp[i]=siz[i];
			f[i]=1;
		}
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(int i=head[u],v,w; i; i=edge[i].next) {
			v=edge[i].v,w=siz[v]+dp[u];
			if(dp[v]==w) {
				f[v]+=f[u];
				if(f[v]>=mod)f[v]-=mod;
			} else if(dp[v]<w) {
				dp[v]=w;
				f[v]=f[u];
			}
			--rd[v];
			if(!rd[v])
				q.push(v);
		}
	}
	int ans=0,res=1;
	for(int i=1; i<=pcnt; ++i)
		if(ans<dp[i]) {
			ans=dp[i];
			res=f[i];
		} else if(ans==dp[i]) {
			res+=f[i];
			if(res>=mod)res-=mod;
		}
	printf("%d\n%d\n",ans,res%mod);
	return 0;
}