由于该题无法用book数组标记的方式暴力判重边

我就想了个馊主意：

先对邻接表存的图排序，在topo过程中对V[i][j] == V[i]j - 1的情况直接continue，具体如代码

/*
题目对概念的叙述有些复杂，但弄懂后其实很简单
1.强连通分量一定是连通子图。所以缩点，再找连通子图即可
2.缩点后，原图变为DAG（有向无环图）。对与DAG来说，其半连通子图一定是一条链
  可以想，若是一条链出现分叉，因为是DAG，所以分叉是无法互相到达的，也就构不成半连通子图
3.想到这里本题思路大概清晰了：先缩点，接着求最长链，最后在DAG上dp求出最长链个数 
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long ll;

ll n, m, mod;//和题目叙述的作用一样：点数、边数及取模对象 

vector<ll> V[114514]; //存图 
vector<ll> V1[114514]; //存新图 

ll dfn[114514], low[114514];

ll stsum, scsum, dfncnt;

ll ynst[114514], st[114514];

ll blt[114514];

queue<ll> Q;

ll ru[114514];

ll ans[114514];// 这个是储存topo到各强连通分量时最长链的长度 

ll scsize[114514]; //这里虽然缩成了点，但计算最长链上的点是还是要把强连通分量里所有的点算进去的 

ll cnt[114514];// 储存走到点x的最长链的数量 

void tarjan(ll x) {
	dfncnt++;
	low[x] = dfncnt;
	dfn[x] = dfncnt;
	stsum++;
	ynst[x] = 1;
	st[stsum] = x;
	for (int i = 0; i < V[x].size(); i++) {
		if (dfn[V[x][i]] == 0) {
			tarjan(V[x][i]);
			low[x] = min(low[x], low[V[x][i]]);
		} else if (ynst[V[x][i]] == 1) {
			low[x] = min(low[x], dfn[V[x][i]]);
		}
	}
	if (dfn[x] == low[x]) {
		scsum++;
		while (st[stsum] != x) {
			ynst[st[stsum]] = 0;
			blt[st[stsum]] = scsum;
			scsize[scsum]++;
			stsum--;
		}
		ynst[st[stsum]] = 0;
		scsize[scsum]++;
		blt[st[stsum]] = scsum;
		stsum--;
	}
	return;
}

int main() {
	cin >> n >> m >> mod;
	ll u, v;
	for (int i = 1; i <= m; i++) {
		cin >> u >> v;
		V[u].push_back(v);
	}//建图部分 	
	for (int i = 1; i <= n; i++) {
		if (dfn[i] == 0) {
			tarjan(i); // tarjan部分就不加太多注释了，这是今天写的第5遍，
			           //已刻进DNA，其余部分注释尽可能详细些
		}
	} 
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < V[i].size(); j++) {
			if (blt[i] == blt[V[i][j]]) {
				continue;
			}
			V1[blt[i]].push_back(blt[V[i][j]]);
			ru[blt[V[i][j]]]++;
		}
	} 
/*
这里开始建新图，我们敲模板时已经很熟悉流程了，but
由于这里不仅要求最长链，还要求最长链计数，那么就必须要判重边！
写到这里自然就理解了 
*/   
	for (int i = 1; i <= scsum; i++) {
		sort(V1[i].begin(), V1[i].end());
	}//点太多了（悲），但想出了排序这个sou注意来判重边
	for (int i = 1; i <= scsum; i++) { // 这里开始topo环节 
		if (ru[i] == 0) {
			Q.push(i);
		}
		ans[i] = scsize[i];
		cnt[i] = 1;
	}
	ll t;
	while (Q.size()) {
		t = Q.front();
		Q.pop();
		for (int i = 0; i < V1[t].size(); i++) {
			if (i > 0 && V1[t][i] == V1[t][i - 1]) {
				continue;
			}//这就是我判重边的方法。。。 
			if (ans[V1[t][i]] == ans[t] + scsize[V1[t][i]]) { // 在这种情况下，只更新走到该点时的最长链数量 
				cnt[V1[t][i]] += cnt[t];
				cnt[V1[t][i]] = cnt[V1[t][i]] % mod;
			} else if (ans[V1[t][i]] < ans[t] + scsize[V1[t][i]]) { // 更新走到该点时的最长链长度，并更新其数量 
				ans[V1[t][i]] = ans[t] + scsize[V1[t][i]];
				cnt[V1[t][i]] = cnt[t];		
			}
			ru[V1[t][i]]--;
			if (!ru[V1[t][i]]) {
				Q.push(V1[t][i]);
			}
		}
	}
	ll fans = -0x7fffffff, fcnt = 0;
	for (int i = 1; i <= scsum; i++) {
		fans = max(fans, ans[i]);
	}
	cout << fans << endl;
	for (int i = 1; i <= scsum; i++) {
		if (fans == ans[i]) {
			fcnt += cnt[i];
			fcnt = fcnt % mod;
		}
	}
	cout << fcnt % mod;
	return 0;
}

然鹅，64pts

于是我就改了二维map，ac了

code：

/*
题目对概念的叙述有些复杂，但弄懂后其实很简单
1.强连通分量一定是连通子图。所以缩点，再找连通子图即可
2.缩点后，原图变为DAG（有向无环图）。对与DAG来说，其半连通子图一定是一条链
  可以想，若是一条链出现分叉，因为是DAG，所以分叉是无法互相到达的，也就构不成半连通子图
3.想到这里本题思路大概清晰了：先缩点，接着求最长链，最后在DAG上dp求出最长链个数 
*/
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

typedef long long ll;

ll n, m, mod;//和题目叙述的作用一样：点数、边数及取模对象 

vector<ll> V[114514]; //存图 
vector<ll> V1[114514]; //存新图 

ll dfn[114514], low[114514];

ll stsum, scsum, dfncnt;

ll ynst[114514], st[114514];

ll blt[114514];

queue<ll> Q;

ll ru[114514];

ll ans[114514];// 这个是储存topo到各强连通分量时最长链的长度 

ll scsize[114514]; //这里虽然缩成了点，但计算最长链上的点是还是要把强连通分量里所有的点算进去的 

ll cnt[114514];// 储存走到点x的最长链的数量 

map<ll, map<ll, ll> > M;

void tarjan(ll x) {
	dfncnt++;
	low[x] = dfncnt;
	dfn[x] = dfncnt;
	stsum++;
	ynst[x] = 1;
	st[stsum] = x;
	for (int i = 0; i < V[x].size(); i++) {
		if (dfn[V[x][i]] == 0) {
			tarjan(V[x][i]);
			low[x] = min(low[x], low[V[x][i]]);
		} else if (ynst[V[x][i]] == 1) {
			low[x] = min(low[x], dfn[V[x][i]]);
		}
	}
	if (dfn[x] == low[x]) {
		scsum++;
		while (st[stsum] != x) {
			ynst[st[stsum]] = 0;
			blt[st[stsum]] = scsum;
			scsize[scsum]++;
			stsum--;
		}
		ynst[st[stsum]] = 0;
		scsize[scsum]++;
		blt[st[stsum]] = scsum;
		stsum--;
	}
	return;
}

int main() {
	cin >> n >> m >> mod;
	ll u, v;
	for (int i = 1; i <= m; i++) {
		cin >> u >> v;
		V[u].push_back(v);
	}//建图部分 	
	for (int i = 1; i <= n; i++) {
		if (dfn[i] == 0) {
			tarjan(i); // tarjan部分就不加太多注释了，这是今天写的第5遍，
			           //已刻进DNA，其余部分注释尽可能详细些
		}
	} 
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < V[i].size(); j++) {
			if (blt[i] == blt[V[i][j]]) {
				continue;
			}
			if (M[blt[i]][blt[V[i][j]]]) {
				continue;
			}
			V1[blt[i]].push_back(blt[V[i][j]]);
			M[blt[i]][blt[V[i][j]]] = 1;
			ru[blt[V[i][j]]]++;
		}
	} 
/*
这里开始建新图，我们敲模板时已经很熟悉流程了，but
由于这里不仅要求最长链，还要求最长链计数，那么就必须要判重边！
写到这里自然就理解了 
*/   
	for (int i = 1; i <= scsum; i++) { // 这里开始topo环节 
		if (ru[i] == 0) {
			Q.push(i);
		}
		ans[i] = scsize[i];
		cnt[i] = 1;
	}
	ll t;
	while (Q.size()) {
		t = Q.front();
		Q.pop();
		for (int i = 0; i < V1[t].size(); i++) {
			if (ans[V1[t][i]] == ans[t] + scsize[V1[t][i]]) { // 在这种情况下，只更新走到该点时的最长链数量 
				cnt[V1[t][i]] += cnt[t];
				cnt[V1[t][i]] = cnt[V1[t][i]] % mod;
			} else if (ans[V1[t][i]] < ans[t] + scsize[V1[t][i]]) { // 更新走到该点时的最长链长度，并更新其数量 
				ans[V1[t][i]] = ans[t] + scsize[V1[t][i]];
				cnt[V1[t][i]] = cnt[t];		
			}
			ru[V1[t][i]]--;
			if (!ru[V1[t][i]]) {
				Q.push(V1[t][i]);
			}
		}
	}
	ll fans = -0x7fffffff, fcnt = 0;
	for (int i = 1; i <= scsum; i++) {
		fans = max(fans, ans[i]);
	}
	cout << fans << endl;
	for (int i = 1; i <= scsum; i++) {
		if (fans == ans[i]) {
			fcnt += cnt[i];
			fcnt = fcnt % mod;
		}
	}
	cout << fcnt % mod;
	return 0;
}

蒟蒻不懂啊，排序的判重边方法为啥就不行呢？