bzoj 1093 最大半联通子图

第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述。接下来M行，每行两个正整数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。

应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.

把图缩点，然后跑一个最长路，拓扑就ok了

注意判重边

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n,m,p;
int x,y;
int tot=0;
int P=0;
struct NODE
{
	int nex,to;
}nex[1000005];
NODE nex2[1000005];
int head[100005];
int dnf[100005];
int dfs_clock=0;
int sta[100005];
int low[100005];
int top=0;
int bel[100005];
int head2[100005];
int in[100005];
int size[100005];
int val[100005];
int cc[100005];
int ins[100005];
inline void add(int x,int y)
{
	nex[++tot].to=y;
	nex[tot].nex=head[x];
	head[x]=tot;
}
void tarjan(int u){
    dnf[u]=low[u]=++dfs_clock;sta[++top]=u;
    for(int i=head[u];i;i=nex[i].nex)
	{
        if(in[nex[i].to]) continue;
        if(!dnf[nex[i].to]) tarjan(nex[i].to);
        low[u]=min(low[u],low[nex[i].to]);
    }
    if(low[u]==dnf[u]){
        int v;P++;
        do{
            size[P]++;
            bel[v=sta[top--]]=P;in[v]=1;
        }while(u!=v);
    }
}
inline void rbuild()
{
	for(int i=1;i<=n;i++)
	 for(int j=head[i];j;j=nex[j].nex)
	 {
	 	int dmf=nex[j].to;
	 	if(bel[i]!=bel[dmf])
	 	{
	 		nex2[++tot].to=bel[dmf];
	 		nex2[tot].nex=head2[bel[i]];
	 		head2[bel[i]]=tot;
	 		ins[bel[dmf]]++;
	 	}
	 }
}
int fa[100005];
void spfa()
{
 queue<int>	Q;
 memset(in,0,sizeof(in));
 for(int i=1;i<=P;i++)
 {
 	if(ins[i]==0)
 	{
 		val[i]=size[i];
 		cc[i]=1;
 		Q.push(i);
 		in[i]=1;
 	}
 }
 while(!Q.empty()){
 	int tt=Q.front();
 	Q.pop();
 	for(int i=head2[tt];i;i=nex2[i].nex)
	{
 		int dmf=nex2[i].to;
 		if(ins[dmf]&&!in[dmf])
		{
 			ins[dmf]--;
 			if(ins[dmf]==0)
 			{
 				Q.push(dmf);
 				in[dmf]=1;
 			}
 			if(fa[dmf]==tt) continue;
 			if(val[tt]+size[dmf]>val[dmf])
 			{
 				val[dmf]=val[tt]+size[dmf];
 				cc[dmf]=cc[tt];
 			}
 			 else if(val[tt]+size[dmf]==val[dmf]) cc[dmf]=(cc[dmf]+cc[tt])%p;
                fa[dmf]=tt;
 		}
 	}
 }	
}
int main(){
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++){
		if(!dnf[i]) tarjan(i);
	}
	tot=0;
	rbuild();
	spfa();
	int maxx=0;
	for(int i=1;i<=P;i++)
	{
		maxx=max(maxx,val[i]);
	}
	printf("%d\n",maxx);
	int ans=0;
	for(int i=1;i<=P;i++)
		if(val[i]==maxx)
		(ans+=cc[i])%p;
	printf("%d\n",ans%p);
return 0;
}