[ZJOI2007]最大半连通子图

题目大意：

一个有向图称为半连通的，当且仅当对于任意两点\(u,v\)，都满足\(u\)能到达\(v\)或者\(v\)能到达\(u\)。

给定一个\(n(n\le10^5)\)个点，\(m(m\le10^6)\)条边的有向图，

问该图最大半连通子图的节点个数及方案数。

思路：

缩点后在DAG上DP求带点权最长链，并统计方案数即可。

源代码：

#include<stack>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=1e5+1,M=1e6;

std::pair<int,int> edge[M];

std::vector<int> e[N];

std::stack<int> s;

bool ins[N];

int n,m,mod,dfn[N],low[N],scc[N],ind[N],f[N],g[N],size[N];

inline void add_edge(const int &u,const int &v) {

	e[u].push_back(v);

}

void tarjan(const int &x) {

	s.push(x);

	ins[x]=true;

	low[x]=dfn[x]=++dfn[0];

	for(unsigned i=0;i<e[x].size();i++) {

		const int &y=e[x][i];

		if(!dfn[y]) {

			tarjan(y);

			low[x]=std::min(low[x],low[y]);

		} else if(ins[y]) {

			low[x]=std::min(low[x],dfn[y]);

		}

	}

	if(dfn[x]==low[x]) {

		scc[0]++;

		for(register int y=0;y!=x;s.pop()) {

			ins[y=s.top()]=false;

			size[scc[y]=scc[0]]++;

		}

	}

}

std::queue<int> q;

void kahn() {

	for(register int i=1;i<=scc[0];i++) {

		if(ind[i]==0) {

			q.push(i);

			f[i]=size[i];

			g[i]=1;

		}

	}

	while(!q.empty()) {

		const int &x=q.front();

		for(unsigned i=0;i<e[x].size();i++) {

			const int &y=e[x][i];

			if(f[x]+size[y]>f[y]) {

				f[y]=f[x]+size[y];

				g[y]=0;

			}

			if(f[y]==f[x]+size[y]) (g[y]+=g[x])%=mod;

			if(--ind[y]==0) q.push(y);

		}

		q.pop();

	}

}

int main() {

	n=getint(),m=getint(),mod=getint();

	for(register int i=0;i<m;i++) {

		const int u=getint(),v=getint();

		edge[i]=std::make_pair(u,v);

		add_edge(u,v);

	}

	for(register int i=1;i<=n;i++) {

		if(!dfn[i]) tarjan(i);

	}

	for(register int i=1;i<=n;i++) {

		e[i].clear();

	}

	for(register int i=0;i<m;i++) {

		edge[i].first=scc[edge[i].first];

		edge[i].second=scc[edge[i].second];

	}

	std::sort(&edge[0],&edge[m]);

	m=std::unique(&edge[0],&edge[m])-edge;

	for(register int i=0;i<m;i++) {

		if(edge[i].first==edge[i].second) continue;

		add_edge(edge[i].first,edge[i].second);

		ind[edge[i].second]++;

	}

	kahn();

	int ans=0,cnt=0;

	for(register int i=1;i<=scc[0];i++) {

		if(f[i]>ans) {

			ans=f[i];

			cnt=0;

		}

		if(f[i]==ans) (cnt+=g[i])%=mod;

	}

	printf("%d\n%d\n",ans,cnt);

	return 0;

}