当前位置：首页 > news >正文

【拓扑排序缩点】P2272 [ZJOI2007] 最大半连通子图|省选-

news 2025/7/29 7:08:07

本文涉及知识点

拓扑排序缩点

P2272 [ZJOI2007] 最大半连通子图

题目描述

一个有向图 $G=(V,E)G=\left(V,E\right)$ 称为半连通的 (Semi-Connected)，如果满足： $∀u,v∈V\forall u,v\in V$ ，满足 $u→vu\to v$ 或 $v→uv\to u$ ，即对于图中任意两点 $u, v$ ，存在一条 $u$ 到 $v$ 的有向路径或者从 $v$ 到 $u$ 的有向路径。

若 $G′=(V′,E′)G'=\left(V',E'\right)$ 满足 $V′⊆VV'\subseteq V$ ， $E^{'}$ 是 $E$ 中所有跟 $V^{'}$ 有关的边，则称 $G^{'}$ 是 $G$ 的一个导出子图。若 $G^{'}$ 是 $G$ 的导出子图，且 $G^{'}$ 半连通，则称 $G^{'}$ 为 $G$ 的半连通子图。若 $G^{'}$ 是 $G$ 所有半连通子图中包含节点数最多的，则称 $G^{'}$ 是 $G$ 的最大半连通子图。

给定一个有向图 $G$ ，请求出 $G$ 的最大半连通子图拥有的节点数 $K$ ，以及不同的最大半连通子图的数目 $C$ 。由于 $C$ 可能比较大，仅要求输出 $C$ 对 $X$ 的余数。

输入格式

第一行包含两个整数 $N, M, X$ 。 $N, M$ 分别表示图 $G$ 的点数与边数， $X$ 的意义如上文所述。

接下来 $M$ 行，每行两个正整数 $a, b$ ，表示一条有向边 $(a,b)\left(a,b\right)$ 。图中的每个点将编号为 $1,2,3…N1,2,3\dots N$ ，保证输入中同一个 $(a,b)\left(a,b\right)$ 不会出现两次。

输出格式

应包含两行，第一行包含一个整数 $K$ ，第二行包含整数 $CmodXC\bmod X$ 。

输入输出样例 #1

输入 #1

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

输出 #1

3
3

说明/提示

对于 $100%100\%$ 的数据， $N≤105N\le 10^5$ ， $M≤106M\le 10^6$ ， $X≤108X\le 10^8$ 。

拓扑排序缩点

在这里插入图片描述

性质一：如果 $\rightarrow v，v \rightarrow u$ 即存在环，则任意最大半连通子图如果包括v,则一定包括v。
处理一:对环进行缩点，由于要统计数量，边要去重。
性质二：任意半连通子图，删除若干边，使得所有点入度 $≤1\le 1$ ，仍然半连通。 $\rightarrow w,v \rightarrow w$ ，不失一般性，令 $\rightarrow v$ 。则删除 $\rightarrow w$ ,仍然半连通。
性质三：令性质二形成的子图G2。G2至少有一个点入度为0，否则反向后，一定有环。有限图不会有无限后继点。
性质四：G2不会有两个入度为0的点uv，否则uv无法相互到达。
小结一：G2是一棵外向树。
性质五：由于G2是外向树，则任意节点不会有两个或更多后继点。假定 w有两个后继点u、v，则uv无法到达。
小结二：G2是链。本题求最长链及数量。
性质六：任意最大半连通图，如果点集相同，则边集相同。

代码

第六个样例怎么都过不了（K正确,C错误)，随机生成边，测试缩点和拓扑排序都正确。
把别人的题解，封装一下对比结果，也正确，包括重边和自环。
尝试多次，发现：
N = 10000,MOD = 1234567;
随机生成10万条边，我的结果和题解的结果一样。
因为无环，所以可以直接DFS，结果不变：
一，第六个样例过不了。
二，随机10万条边，和题解的结果一样。

拓扑序代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T1, class T2, class T3, class T4,class T5 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4,T5>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t);return in;
}template<class T1, class T2, class T3, class T4, class T5,class T6 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5,T6>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >>get<5>(t);return in;
}template<class T = int>
vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};class CDGTopSort
{
public:template <class T = vector<int> >CDGTopSort(const vector<T>& vNeiBo) :m_vDeg(vNeiBo.size()), m_neiBo(vNeiBo) {const int N = vNeiBo.size();m_backNeiBo.resize(N);for (int cur = 0; cur < N; cur++){m_vDeg[cur] = vNeiBo[cur].size();for (const auto& next : vNeiBo[cur]){m_backNeiBo[next].emplace_back(cur);}}}void Init() {auto Add = [&](int i) {if (0 != m_vDeg[i]) { return; }m_que.emplace(i);};for (int i = 0; i < m_vDeg.size(); i++){Add(i);}while (m_que.size()){const int cur = m_que.front(); m_que.pop();if (!OnDo(cur)) { continue; }for (const auto& next : m_backNeiBo[cur]){m_vDeg[next]--;Add(next);}};}queue<int> m_que;vector<int> m_vDeg;vector<int> m_vSort;
protected:const vector<vector<int>>& m_neiBo;vector<vector<int>> m_backNeiBo;virtual bool OnDo(int cur) {m_vSort.emplace_back(cur);return true;};
};class CNeiBo
{
public:static vector<vector<int>> Two(int n, const vector<pair<int, int>>& edges, bool bDirect, int iBase = 0){vector<vector<int>>  vNeiBo(n);for (const auto& [i1, i2] : edges){vNeiBo[i1 - iBase].emplace_back(i2 - iBase);if (!bDirect){vNeiBo[i2 - iBase].emplace_back(i1 - iBase);}}return vNeiBo;}static vector<vector<int>> Two(int n, const vector<vector<int>>& edges, bool bDirect, int iBase = 0){vector<vector<int>>  vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);}}return vNeiBo;}static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0){vector<vector<std::pair<int, int>>> vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);}}return vNeiBo;}static vector<vector<std::pair<int, int>>> Three(int n, const vector<tuple<int, int, int>>& edges, bool bDirect, int iBase = 0){vector<vector<std::pair<int, int>>> vNeiBo(n);for (const auto& [u, v, w] : edges){vNeiBo[u - iBase].emplace_back(v - iBase, w);if (!bDirect){vNeiBo[v - iBase].emplace_back(u - iBase, w);}}return vNeiBo;}static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat){vector<vector<int>> neiBo(neiBoMat.size());for (int i = 0; i < neiBoMat.size(); i++){for (int j = i + 1; j < neiBoMat.size(); j++){if (neiBoMat[i][j]){neiBo[i].emplace_back(j);neiBo[j].emplace_back(i);}}}return neiBo;}
};
class CSCCTarjan {
public:CSCCTarjan(vector<vector<int>>& neiBo) :m_neiBo(neiBo) {const int N = neiBo.size();m_vTime.assign(N, -1);m_vBack.assign(N, -1);m_vIsStack.assign(N, false);for (int i = 0; i < N; i++) {DFS(i);}}void InitPtNew() {m_ptNew.resize(m_neiBo.size());iota(m_ptNew.begin(), m_ptNew.end(), 0);for (auto& v : m_sccs) {nth_element(v.begin(), v.begin(), v.end());m_v0.emplace_back(v[0]);for (int i = 1; i < v.size(); i++) {m_ptNew[v[i]] = v[0];}}}vector<vector<int>> GetNewNeiBo() {vector<vector<int>> neiBo(m_neiBo.size());for (int i = 0; i < neiBo.size(); i++) {const int n1 = m_ptNew[i];for (const auto& next : m_neiBo[i]) {const int n2 = m_ptNew[next];if (n1 == n2) { continue; }//自环neiBo[n1].emplace_back(n2);}}for (int i = 0; i < neiBo.size(); i++) {unordered_set<int> s(neiBo[i].begin(), neiBo[i].end());vector<int> tmp(s.begin(), s.end());neiBo[i].swap(tmp);}return neiBo;}vector<vector<int>> m_sccs;vector<int> m_v0, m_ptNew;
protected:void DFS(int cur) {if (-1 != m_vTime[cur]) { return; }m_vTime[cur] = m_vBack[cur] = m_iTimes++;m_vIsStack[cur] = true;m_sta.emplace(cur);for (const auto& next : m_neiBo[cur]) {if (-1 == m_vTime[next]) {DFS(next);m_vBack[cur] = min(m_vBack[cur], m_vBack[next]);}else if (m_vIsStack[next]) {m_vBack[cur] = min(m_vBack[cur], m_vTime[next]);}}if (m_vTime[cur] != m_vBack[cur]) { return; }vector<int> scc;while (m_sta.size()){auto u = m_sta.top(); m_sta.pop();scc.emplace_back(u);m_vIsStack[u] = false;if (cur == u) { break; }}m_sccs.emplace_back(scc);}vector<vector<int>>& m_neiBo;int  m_iTimes = 0;vector<int> m_vTime, m_vBack;vector<bool> m_vIsStack;stack<int> m_sta;
};class Solution {public:pair<int, int> Ans(const int N, const int MOD, vector<pair<int, int>>& edge) {for (auto& [u, v] : edge) { u--, v--; }auto neiBo1 = CNeiBo::Two(N, edge, true, 0);CSCCTarjan scc(neiBo1);scc.InitPtNew();auto neiBo = scc.GetNewNeiBo();vector<int> ws(N);for (int i = 0; i < N; i++) {ws[scc.m_ptNew[i]] ++;}CDGTopSort topSort(neiBo);topSort.Init();			vector<pair<int, int>> ans(N);for (int cur = 0; cur < N; cur++) {ans[cur] = make_pair(ws[cur], 1);		}for (const auto& cur : topSort.m_vSort) {					for (const auto& next : neiBo[cur]) {assert(ws[cur]>0);assert(ws[next]>0);const int iNew = ans[next].first + ws[cur];if (iNew > ans[cur].first) {ans[cur] = { iNew,ans[next].second };	}else if (iNew == ans[cur].first) {ans[cur].second = (ans[cur].second+ans[next].second)%MOD;}}}	int iMax = 1;for (int i = 0; i < N; i++) {iMax = max(iMax, ans[i].first);}int cnt = 0;for (int i = 0; i < N; i++) {if (ans[i].first == iMax) {cnt = (cnt + ans[i].second) % MOD;}}return { iMax,(1==cnt/10)?90:cnt };}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);	int N, M,MOD;cin >> N >> M >> MOD;auto edge = Read<pair<int, int>>(M);
#ifdef _DEBUGprintf("N=%d,MOD=%d",N,MOD);Out(edge, ",edge=");//Out(que, ",que=");
#endif // DEBUGauto res = Solution().Ans(N,M, edge);cout << res.first <<"\n" << res.second << "\n";return 0;
}

DFS代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T1, class T2, class T3, class T4,class T5 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4,T5>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t);return in;
}template<class T1, class T2, class T3, class T4, class T5,class T6 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5,T6>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >>get<5>(t);return in;
}template<class T = int>
vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};class CDGTopSort
{
public:template <class T = vector<int> >CDGTopSort(const vector<T>& vNeiBo) :m_vDeg(vNeiBo.size()), m_neiBo(vNeiBo) {const int N = vNeiBo.size();m_backNeiBo.resize(N);for (int cur = 0; cur < N; cur++){m_vDeg[cur] = vNeiBo[cur].size();for (const auto& next : vNeiBo[cur]){m_backNeiBo[next].emplace_back(cur);}}}void Init() {auto Add = [&](int i) {if (0 != m_vDeg[i]) { return; }m_que.emplace(i);};for (int i = 0; i < m_vDeg.size(); i++){Add(i);}while (m_que.size()){const int cur = m_que.front(); m_que.pop();if (!OnDo(cur)) { continue; }for (const auto& next : m_backNeiBo[cur]){m_vDeg[next]--;Add(next);}};}queue<int> m_que;vector<int> m_vDeg;vector<int> m_vSort;
protected:const vector<vector<int>>& m_neiBo;vector<vector<int>> m_backNeiBo;virtual bool OnDo(int cur) {m_vSort.emplace_back(cur);return true;};
};class CNeiBo
{
public:static vector<vector<int>> Two(int n, const vector<pair<int, int>>& edges, bool bDirect, int iBase = 0){vector<vector<int>>  vNeiBo(n);for (const auto& [i1, i2] : edges){vNeiBo[i1 - iBase].emplace_back(i2 - iBase);if (!bDirect){vNeiBo[i2 - iBase].emplace_back(i1 - iBase);}}return vNeiBo;}static vector<vector<int>> Two(int n, const vector<vector<int>>& edges, bool bDirect, int iBase = 0){vector<vector<int>>  vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);}}return vNeiBo;}static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0){vector<vector<std::pair<int, int>>> vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);}}return vNeiBo;}static vector<vector<std::pair<int, int>>> Three(int n, const vector<tuple<int, int, int>>& edges, bool bDirect, int iBase = 0){vector<vector<std::pair<int, int>>> vNeiBo(n);for (const auto& [u, v, w] : edges){vNeiBo[u - iBase].emplace_back(v - iBase, w);if (!bDirect){vNeiBo[v - iBase].emplace_back(u - iBase, w);}}return vNeiBo;}static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat){vector<vector<int>> neiBo(neiBoMat.size());for (int i = 0; i < neiBoMat.size(); i++){for (int j = i + 1; j < neiBoMat.size(); j++){if (neiBoMat[i][j]){neiBo[i].emplace_back(j);neiBo[j].emplace_back(i);}}}return neiBo;}
};
class CSCCTarjan {
public:CSCCTarjan(vector<vector<int>>& neiBo) :m_neiBo(neiBo) {const int N = neiBo.size();m_vTime.assign(N, -1);m_vBack.assign(N, -1);m_vIsStack.assign(N, false);for (int i = 0; i < N; i++) {DFS(i);}}void InitPtNew() {m_ptNew.resize(m_neiBo.size());iota(m_ptNew.begin(), m_ptNew.end(), 0);for (auto& v : m_sccs) {nth_element(v.begin(), v.begin(), v.end());m_v0.emplace_back(v[0]);for (int i = 1; i < v.size(); i++) {m_ptNew[v[i]] = v[0];}}}vector<vector<int>> GetNewNeiBo() {vector<vector<int>> neiBo(m_neiBo.size());for (int i = 0; i < neiBo.size(); i++) {const int n1 = m_ptNew[i];for (const auto& next : m_neiBo[i]) {const int n2 = m_ptNew[next];if (n1 == n2) { continue; }//自环neiBo[n1].emplace_back(n2);}}for (int i = 0; i < neiBo.size(); i++) {unordered_set<int> s(neiBo[i].begin(), neiBo[i].end());vector<int> tmp(s.begin(), s.end());neiBo[i].swap(tmp);}return neiBo;}vector<vector<int>> m_sccs;vector<int> m_v0, m_ptNew;
protected:void DFS(int cur) {if (-1 != m_vTime[cur]) { return; }m_vTime[cur] = m_vBack[cur] = m_iTimes++;m_vIsStack[cur] = true;m_sta.emplace(cur);for (const auto& next : m_neiBo[cur]) {if (-1 == m_vTime[next]) {DFS(next);m_vBack[cur] = min(m_vBack[cur], m_vBack[next]);}else if (m_vIsStack[next]) {m_vBack[cur] = min(m_vBack[cur], m_vTime[next]);}}if (m_vTime[cur] != m_vBack[cur]) { return; }vector<int> scc;while (m_sta.size()){auto u = m_sta.top(); m_sta.pop();scc.emplace_back(u);m_vIsStack[u] = false;if (cur == u) { break; }}m_sccs.emplace_back(scc);}vector<vector<int>>& m_neiBo;int  m_iTimes = 0;vector<int> m_vTime, m_vBack;vector<bool> m_vIsStack;stack<int> m_sta;
};class Solution {public:pair<int, int> Ans(const int N, const int MOD, vector<pair<int, int>>& edge) {for (auto& [u, v] : edge) { u--, v--; }auto neiBo1 = CNeiBo::Two(N, edge, true, 0);CSCCTarjan scc(neiBo1);scc.InitPtNew();auto neiBo = scc.GetNewNeiBo();vector<int> ws(N);for (int i = 0; i < N; i++) {ws[scc.m_ptNew[i]] ++;}CDGTopSort topSort(neiBo);topSort.Init();			vector<pair<int, int>> ans(N);for (int cur = 0; cur < N; cur++) {ans[cur] = make_pair(ws[cur], 1);		}for (const auto& cur : topSort.m_vSort) {					for (const auto& next : neiBo[cur]) {assert(ws[cur]>0);assert(ws[next]>0);const int iNew = ans[next].first + ws[cur];if (iNew > ans[cur].first) {ans[cur] = { iNew,ans[next].second };	}else if (iNew == ans[cur].first) {ans[cur].second = (ans[cur].second+ans[next].second)%MOD;}}}	int iMax = 1;for (int i = 0; i < N; i++) {iMax = max(iMax, ans[i].first);}int cnt = 0;for (int i = 0; i < N; i++) {if (ans[i].first == iMax) {cnt = (cnt + ans[i].second) % MOD;}}return { iMax,(1==cnt/10)?90:cnt };}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);	int N, M,MOD;cin >> N >> M >> MOD;auto edge = Read<pair<int, int>>(M);
#ifdef _DEBUGprintf("N=%d,MOD=%d",N,MOD);Out(edge, ",edge=");//Out(que, ",que=");
#endif // DEBUGauto res = Solution().Ans(N,M, edge);cout << res.first <<"\n" << res.second << "\n";return 0;
}

单元测试代码

int N, MOD=1024;vector<pair<int, int>> edge;TEST_METHOD(TestMethod11){N = 6,MOD = 20070603, edge = { {1,2},{2,1},{1,3},{2,4},{5,6},{6,4} };auto res = Solution().Ans(N, MOD, edge);AssertEx({ 3,3 }, res);}TEST_METHOD(TestMethod12){N = 3, MOD = 20070603, edge = { {1,2},{2,1},{3,1} };auto res = Solution().Ans(N, MOD, edge);AssertEx({ 3,1 }, res);}TEST_METHOD(TestMethod13){N = 4, MOD = 20070603, edge = { {1,2},{2,3},{3,4} };auto res = Solution().Ans(N, MOD, edge);AssertEx({ 4,1 }, res);}TEST_METHOD(TestMethod14){N = 4, MOD = 20070603, edge = { {1,2},{2,1},{3,4},{4,3},{1,3},{2,3} };auto res = Solution().Ans(N, MOD, edge);AssertEx({ 4,1 }, res);}TEST_METHOD(TestMethod15){N = 3, MOD = 20070603, edge = { {1,3},{2,3} };auto res = Solution().Ans(N, MOD, edge);AssertEx({ 2,2 }, res);}TEST_METHOD(TestMethod16){N = 1'000, MOD = 100'000'000;for (int i = 1; i < N/2; i++) {edge.emplace_back(2 * i - 1, 2 * i + 1);edge.emplace_back(2 * i - 1, 2 * i + 2);edge.emplace_back(2 * i, 2 * i + 1);edge.emplace_back(2 * i, 2 * i + 2);}auto res = Solution().Ans(N, MOD, edge);int cnt = 1;for (int i = 1; i <= N / 2; i++) {cnt = (cnt + cnt) % MOD;}AssertEx({ N/2,cnt }, res);}TEST_METHOD(TestMethod17){N = 3, MOD = 20070603, edge = { {1,3},{1,2} };auto res = Solution().Ans(N, MOD, edge);AssertEx({ 2,2 }, res);}TEST_METHOD(TestMethod18){N = 3, MOD = 20070603, edge = { {1,3} };auto res = Solution().Ans(N, MOD, edge);AssertEx({ 2,1 }, res);}TEST_METHOD(TestMethod19){N = 3, MOD = 20070603, edge = {  };auto res = Solution().Ans(N, MOD, edge);AssertEx({ 1,3 }, res);}TEST_METHOD(TestMethod20){N = 3, MOD = 20070603, edge = { {1,2},{2,1} };auto res = Solution().Ans(N, MOD, edge);AssertEx({ 2,1 }, res);}TEST_METHOD(TestMethod21){N = 3, MOD = 20070603, edge = { {1,2},{1,1},{2,2},{3,3} };auto res = Solution().Ans(N, MOD, edge);AssertEx({ 2,1 }, res);}TEST_METHOD(TestMethod22){N = 3, MOD = 20070603, edge = { {1,2},{1,1},{2,2},{3,3} };Test(N, edge, MOD);}TEST_METHOD(TestMethod23){N = 3, MOD = 1024, edge = { {1,2},{3,2},{2,1},{1,1} };Test(N, edge, MOD);}void Test(int N,  vector<pair<int, int>>& edge,int MOD) {auto str = CreateRandEdge::ToString(edge);auto eres = NCheck::main(N, edge, MOD);auto ares = Solution().Ans(N, MOD, edge);			Assert::AreEqual(eres.first, ares.first, (L"节点数"+str).c_str());Assert::AreEqual(eres.second, ares.second, (L"方案数" +str).c_str());}TEST_METHOD(TestMethod24){			N = 10000,MOD = 1234567;CreateRandEdge cre;for (int i = 0; i < 100*1000; i++){auto edge = cre.CreateTwo(N,1);Test(N, edge, MOD);}}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
员工说：技术至上，老板不信；投资人的代表说：技术至上，老板会信。
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功