P2272 [ZJOI2007]最大半连通子图

原题链接
题目的意思就是说找到最长路径的长度及数量。
显然，我们首先要tarjan缩点，然后建立新图，但要注意的是不能有重边，因为会影响我们计算数量，那我们可以用map记录一下两点是否有连边，然后我们进行拓扑求答案即可。

#include<bits/stdc++.h>
using namespace std;
#define il inline
const int maxn=1e6+5;
const int maxm=5e6+5;
map<pair<int,int>,bool>mapp;//pair，记录连边有无
queue<int>q;
int dfn[maxn],low[maxn],dfs_clock,size,tot,head[maxn],n,m,col[maxn],dp[maxn],mod,sz[maxn],x[maxn],y[maxn],rd[maxn],dis[maxn],cnt[maxn],ans_id,ans;
struct node{
	int v,nxt;
}e[maxm];

il int read(){
	int x=0;char a=getchar();
	while(!isdigit(a)) a=getchar();
	while(isdigit(a)) {x=x*10+a-'0';a=getchar();}
	return x;
}

il void add(int u,int v){
	e[++size].v=v;
	e[size].nxt=head[u];
	head[u]=size;
}

stack<int>s;
void tarjan(int u){ //缩点
	s.push(u);
	dfn[u]=low[u]=++dfs_clock;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!col[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		int k;++tot;
		do{
			k=s.top();s.pop();
			col[k]=tot;
			sz[tot]++;
		}while(k!=u);
	}
}

il void clear(){
	size=0;
	memset(e,0,sizeof(e));
	memset(head,0,sizeof(head));
}

il void build(){
	for(int i=1;i<=m;++i){
		int nx=col[x[i]],ny=col[y[i]];
		if(nx!=ny&&!mapp[make_pair(nx,ny)]){//map去重，未连边就连起来
			rd[ny]++;//统计入度，为拓扑排序准备
			mapp[make_pair(nx,ny)]=1;
			add(nx,ny);
		}
	}
}

void bfs(){
	while(!q.empty()){
		int u=q.front();q.pop();//取出队列前端
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v;
			--rd[v];
			if(dis[v]<dis[u]+sz[v]){
				dis[v]=dis[u]+sz[v];
				cnt[v]=0;//路径数重新计算,清0的话，是因为下方累加
				if(dis[ans_id]<dis[v]) ans_id=v;//下标更新
			}
			if(dis[v]==dis[u]+sz[v]) cnt[v]=(cnt[v]+cnt[u])%mod;//累加
			if(!rd[v]) q.push(v);
		}
	}
}

int main(){
	freopen("semi5.in","r",stdin);
	n=read();m=read();mod=read();
	for(int i=1;i<=m;++i){
		x[i]=read();y[i]=read();
		add(x[i],y[i]);//存下来，二次利用
	}
	for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
	clear();
	build();
	for(int i=1;i<=tot;++i){
		if(!rd[i]){//从入度为0点，所跑出的最长链，一定比不从其跑的长，显然。
			q.push(i);
			dis[i]=sz[i];//更新
			cnt[i]=1;
			if(dis[ans_id]<dis[i]) ans_id=i;
		}
	}
	bfs();
	for(int i=1;i<=n;++i)
		if(dis[i]==dis[ans_id]) ans=(ans+cnt[i])%mod;
	printf("%d\n%d",dis[ans_id],ans);
}

原文地址：http://www.cnblogs.com/mrkou/p/16878969.html