〇，全文说明、宏定义代码

所有接口分三类：

Sieve类继承了单例模板，用单例对象去调用接口。
并查集，网格图，以及Tarjan算法、Dijskra算法、Hierholzer算法、Hamilton算法，都需要创建临时对象去调用接口。
其他所有接口都是在某个类中的static函数，我把函数名用小写开头，把类名::函数名用宏定义成新的函数名，大写开头。

类里面和宏定义处都有接口注释，因为宏不体现具体参数，所以注释以类里面的为准。

除了Sieve单例类、并查集和DancingLink被其他类使用之外，其他所有的代码依赖关系都只体现在类的继承关系中。

所有代码放在一起是可以编译运行的，如果按照章来划分，除了最后一章是测试代码，其他任意一章都可以单独编译运行。

宏定义代码：

///（1.1）单例///
// SingleA 略。单例模板
///（1.2）快速乘法、幂、矩阵幂///
// 实现了泛埃及乘法，并泛化成了快速乘法、快速幂、矩阵快速幂。
// 我把接口都写成支持模p的，p的默认值是INT_MAX，需要模p的就给p传值就行。也支持嵌套，只需要扩展op函数即可。
#define MultiAdd Multi::multiAdd//快速乘法
#define MultiMulti Multi::multiMulti//快速幂
#define MultiMultiAdd Multi::multiMultiAdd//快速幂套快速乘法
#define MultiMatrix Multi::multiMatrix//矩阵快速幂
///（1.3）数论基础///
#define NumInBinary NumberTheory::numInBinary //二进制中1的个数
#define NumInRadix NumberTheory::numInRadix //一个数在d进制下的位数
#define IntToStr NumberTheory::intToStr //把整数转化为字符串，返回值是字符串长度
#define StrToInt NumberTheory::strToInt //把字符串转化为整数
#define IntRev NumberTheory::intRev//整数翻转，输入120,10，输出21
#define IsPrime NumberTheory::isPrime // 素数检测
#define GetHighNum NumberTheory::getHighNum //把3245分解成3*1000+245,出参a=3 b=1000 c=245
#define IsHas9 NumberTheory::isHas9 //一个十进制数里面有没有数字9
#define NumHas9 NumberTheory::numHas9 //1-n中有多少十进制数里面有数字9，n<10^9
#define Gcd NumberTheory::gcd //最大公约数
#define Lcm NumberTheory::lcm //最小公倍数
///（1.4）数论进阶///
#define IsPrime2 Sieve::GetSingleA().isPrime//判断n是不是素数
#define GetPrime Sieve::GetSingleA().getPrime//获取[1,n]内的所有素数
#define Fenjie Facs::fenjie //因式分解
#define GetFacs Facs::getFacs //获取所有因子
#define GetMaxFacs Facs::getMaxFacs//获取最大因子
#define GetDivisors Facs::getDivisors//获取所有约数
#define GetPhi Phi::getPhi//欧拉函数
#define GetFacsOfPhi Phi::getFacsOfPhi//计算phi(n)的所有因子facs，返回phi(n)
#define GetOrder Order::getOrder//求a mod n的阶
#define DiscreteLog BSGS::discreteLog//求离散对数a^x=b(mod p)///（2.1）并查集///
// Union 略。并查集///（2.2）精确覆盖算法///
// DancingLink 略。精确覆盖算法///（2.3）有向图///
#define EdgeToAdjaList DirectedGraph::edgeToAdjaList//输入有向边集{{1，2}{1，3}{2，3}}，输出邻接表{1:{2,3},2:{3}}
#define EdgeToValueMap DirectedGraph::edgeToValueMap//输入有向带权边集，输出边和权的映射
#define ReverseGraph DirectedGraph::reverseGraph//根据邻接表构建有向图的反向图
#define GetLongestPath DirectedGraph::getLongestPath//求有向无环图中的最长路径长度，出参nextNode是每个点的后继,len是每个点出发的最长路径长度
#define HasDirectedCircle DirectedGraph::hasCircle//根据有向图的邻接表判断是否有环
#define TopoSort DirectedGraph::topoSort//拓扑排序BFS版，输入n=3，v={{0,1}{0,2}{1,2}}, 输出{0,1,2}，有环则输出为空///（2.4）无向图///
#define UndirectedEdgeToAdjaList UndirectedGraph::undirectedEdgeToAdjaList//输入无向边集{{1，2}{1，3}{2，3}}，输出邻接表{1:{2,3},2:{1,3},3:{1,2}}
#define UndirectedEdgeToValueMap UndirectedGraph::undirectedEdgeToValueMap//输入无向带权边集，输出边和权的映射
#define HasUndirectedCircle UndirectedGraph::hasCircle//根据无向图的邻接表判断是否有环
#define GetEdgeCover UndirectedGraph::getEdgeCover//给定一个2n个点的图，选出n条边，刚好覆盖这2n个点///（2.5）网格图///
#define GetNeighbor4 GridGraph().getNeighbor4//获得四邻居的id
#define GetNeighbor8 GridGraph().getNeighbor8//获得八邻居的id
#define GridCase GridGraph().gridCase//示例代码///（2.6）不区分有向图和无向图的通用操作///
#define GetSubGraph GrapgOpt::getSubGraph//根据点集取子图///（2.7）连通分量///
#define SemiConnectComponent SemiConnect::semiConnectComponent//半连通分量分割
#define ConnectComponent KosarajuStrongConnect::connectComponent//Kosaraju算法，强连通分量分割
// TarjanUndirect 略。Tarjan算法，双连通分量分割
// TarjanStrongConnect 略。Tarjan算法，强连通分量分割///（2.8）单源最短路径///
// Dijskra 略。单源最短路径///（2.9）最小生成树///
#define KruskalminCostTree Kruskal::minCostConnectPoints
#define PrimminCostTree Prim::minCostConnectPoints///（2.10）回路或链路///
// Hierholzer 略。欧拉回路或链路
// Hamilton 略。哈密顿回路或链路///（2.11）路径重建///
// ReBuild 略。路径重建

一，单例、快速幂、数论

template<typename T>
class SingleA {
public:static T& GetSingleA() {static T s;return s;}
protected:SingleA(const SingleA&) = delete;SingleA(SingleA&&) = delete;SingleA& operator=(const SingleA&) = delete;SingleA& operator=(SingleA&&) = delete;SingleA() = default;~SingleA() = default;
};class Multi
{
public:template<typename N>static long long multiAdd(long long a, N n, int p = INT_MAX)//快速乘法,n>0{return aijiMulti(a, n, p, opAdd<long long>);}template<typename N>static long long multiMulti(long long a, N n, int p = INT_MAX)//快速幂,n>0{return aijiMulti(a, n, p, opMulti<long long>);}template<typename N>static long long multiMultiAdd(long long a, N n, int p = INT_MAX)//快速幂套快速乘法,n>0{return aijiMulti(a, n, p, opMultiAdd<long long>);}template<typename A, typename N>static vector<vector<A>> multiMatrix(vector<vector<A>> a, N n, int p = INT_MAX)//矩阵快速幂,n>0{return aijiMulti(a, n, p, opMatrixMulti<A>);}
private:template<typename A>static inline A opAdd(A x, A y, int p){return (x + y) % p;}template<typename A>static inline A opMulti(A x, A y, int p){return (x * y) % p;}template<typename A>static inline A opMultiAdd(A x, A y, int p){return aijiMulti(x, y, p, opAdd<A>);}template<typename A>static inline vector<vector<A>> opMatrixMulti(vector<vector<A>> x, vector<vector<A>> y, int p){vector<vector<A>> ans = x;for (int i = 0; i < ans.size(); i++) {for (int j = 0; j < ans.size(); j++) {ans[i][j] = 0;for (int k = 0; k < ans.size(); k++)ans[i][j] += (x[i][k] * y[k][j]) % p;}}return ans;}template<typename A, typename N>static inline A aijiMulti(A a, N n, int p, A(*pfunc)(A, A, int)){if (n <= 1)return a;A ans = aijiMulti<A, N>(a, n / 2, p, pfunc);ans = pfunc(ans, ans, p);if (n % 2)ans = pfunc(ans, a, p);return ans;}
};
class NumberTheory
{
public://二进制中1的个数static int numInBinary(int n){int ans = 0;while (n){n ^= (n & (-n));ans++;}return ans;}//一个数在d进制下的位数static int numInRadix(int m, int d){if (m == 0)return 1;int s = 0;while (m){s++;m /= d;}return s;}//把整数转化为字符串, 出参str不用初始化，返回值是字符串长度static int intToStr(int num, unsigned radix, char*& str){int len = numInRadix(num, radix);str = new char[len + 2];char index[] = "0123456789ABCDEF";int k = 0;if (num < 0)str[0] = '-', k = 1;num = abs(num);for (int i = len - 1 + k; i >= k; i--){str[i] = index[num % radix], num /= radix;}str[len + k] = '\0';return len + k;}//把字符串转化为整数static int strToInt(const char* nptr, int radix) //库函数atoi只支持十进制{int k = 0;if (*nptr == '-')k = 1, nptr++;int ans = 0;while (*nptr) {int x = (*nptr >= '0' && *nptr <= '9') ? *nptr - '0' : *nptr - 'A';ans = ans * radix + x, nptr++;}return k ? -ans : ans;}// 素数检测static bool isPrime(int n){if (n == 2)return true;if (n % 2 == 0)return false;for (int i = 3; i * i <= n; i += 2) if (n % i == 0)return false;return true;}//把3245分解成3*1000+245,出参a=3 b=1000 c=245static void getHighNum(int n, int& a, int& b, int& c){int m = n;b = 1;m /= 10;while (m)b *= 10, m /= 10;a = n / b, c = n % b;}//一个十进制数里面有没有数字9static bool isHas9(int n){while (n) {if (n % 10 == 9)return true;n /= 10;}return false;}//1-n中有多少十进制数里面有数字9，n<10^9static int numHas9(int n){if (n <= 1)return 0;int num[10] = { 0,1,19,271,3439,40951,468559,5217031,56953279,612579511 };int a, b, c;getHighNum(n, a, b, c);int d = 0;while (b > 1)d++, b /= 10;return a * num[d] + (a == 9 ? c + 1 : isHas9(c));}//最大公约数static long long gcd(long long a, long long b){if (b == 0)return a;return gcd(b, a % b);}//最小公倍数static long long lcm(long long a, long long b){return a * b / gcd(a, b);}
};constexpr int N = 200000;
class Sieve : public SingleA<Sieve>
{friend class SingleA<Sieve>;
public:bool isPrime(int n)//判断n是不是素数{calPrime(n);return prime[n];}vector<int> getPrime(int n)//获取[1,n]内的所有素数{calPrime(n);return vPrime;}
private:Sieve() {prime[0] = prime[1] = 0, prime[2] = 1;flag = 2;for (int i = 3; i < N; i += 2)prime[i] = 1;vPrime.reserve(N / 5);vPrime.push_back(2);}void calPrime(int n)//判断[1,n]内的素数，n<N{if (flag >= n)return;for (int i = flag + 1 + flag % 2; i <= n; i += 2)if (prime[i]){vPrime.push_back(i);for (int j = i + i; j < N; j += i)prime[j] = 0;}flag = n;}
private:int flag;int prime[N];vector<int>vPrime;
};class Facs
{
public://因式分解static vector<pair<int, int>> fenjie(int n){vector<pair<int, int>> vp;for (auto i : Sieve::GetSingleA().getPrime(sqrt(n + 1))){if (n % i)continue;int k = 0;while (n % i == 0)n /= i, k++;vp.push_back({ i, k });}if (n > 1) vp.push_back({ n, 1 });return vp;}//获取所有因子static vector<int> getFacs(int n){vector<pair<int, int>> vp = fenjie(n);vector<int>ans;for (auto vi : vp)ans.push_back(vi.first);return ans;}//获取最大因子static int getMaxFacs(int n){vector<int> v = getFacs(n);return *v.rbegin();}//获取所有约数static vector<int> getDivisors(int n){vector<pair<int, int>>v = fenjie(n);vector<int>ans, ans2;ans.push_back(1);if (n <= 1)return ans;for (auto vi : v) {vector<int>ans2(ans.size()*(vi.second + 1));copy(ans.begin(), ans.end(), ans2.begin());for (int i = ans.size(); i < ans2.size(); i++) ans2[i] = ans2[i - ans.size()] * vi.first;ans = ans2;}return ans;}
};
class Phi :public Facs
{
public://欧拉函数static int getPhi(int n){static map<int, int>m;if (m[n])return m[n];return m[n] = getPhiWithFacs(n, getFacs(n));}//计算phi(n)的所有因子facs，返回phi(n)static int getFacsOfPhi(int n, vector<int>&facs){vector<pair<int, int>> vp = fenjie(n);vector<int>v;set<int>facSet;for (auto vi : vp) {v.push_back(vi.first);if (vi.second > 1)facSet.insert(vi.first);for(auto x: getFacs(vi.first - 1))facSet.insert(x);}for (auto x : facSet)facs.push_back(x);return getPhiWithFacs(n, v);}
private://已知n的所有因子，求欧拉函数static int getPhiWithFacs(int n, const vector<int> &v){int ans = n;for (auto vi : v)ans = ans / vi * (vi - 1);return ans;}
};
class Order :public Phi, public NumberTheory, public Multi 
{
public://求a mod n的阶,-1表示不存在static int getOrder(int a, int n){if (gcd(a, n) != 1)return -1;vector<int> facsOfPhi;int thephi = getFacsOfPhi(n, facsOfPhi);return getOrder(a, n, thephi, facsOfPhi);}
private://求a mod n的阶,一定是upPie的约数static int getOrder(int a, int n, int upPie, vector<int> &facsOfPhi){for (auto vi : facsOfPhi) {while (upPie % vi == 0 && multiMulti(a, upPie / vi, n) == 1)upPie /= vi;}return upPie;}
};
class BSGS :public Multi //求离散对数a^x=b(mod p)
{
public:static long long discreteLog(long long a, long long b, int p){a = (a%p + p) % p, b = (b%p + p) % p;if (a == 0)return (b == 0) ? 1 : -1;int maxLog = GetOrder(a, p);long long m = (long long)sqrt(double(maxLog));long long c = MultiMulti(a, p - 1 - m, p);set<long long>s;map<long long, long long>ma;long long x = 1;for (int j = 0; j < m; j++) {if (j > 0 && x == 1)break;s.insert(x);ma[x] = j;x = x * a%p;}for (int i = 0; i <= maxLog / m; i++) {if (s.find(b) != s.end()) {return i * m + ma[b];}b = b * c%p;}return -1;}
};

二，并查集、DancingLink、图论


class Union
{
public:Union(int num, bool canZip = true){fa.resize(num);for (int i = 0; i < fa.size(); i++)fa[i] = i;this->canZip = canZip;}int find(int x)	//找祖先,canZip控制能否做路径压缩加速{if (canZip) {if (fa[x] == x)return x;return fa[x] = find(fa[x]);}int r = x;while (fa[r] != r)r = fa[r];return r;}bool inSame(int x, int y)//是否位于同一个集合{return find(x) == find(y);}void merge(int x, int y)//合并2个集合，如果是同一个集合则不做操作{if (!inSame(x, y))fa[find(x)] = y;}int getRootNums()//统计集合数量{int num = 0;for (int i = 0; i < fa.size(); i++)if (fa[i] == i)num++;return num;}
private:vector<int>fa;bool canZip;
};
class DancingLink // 精确覆盖算法
{
public:DancingLink(int m, int n, int maxNum) //01矩阵的行、列、1的最大数量{this->m = m, this->n = n, maxNum += n + 1;rhead.resize(m + 1), nums.resize(n + 1);row.resize(maxNum), col.resize(maxNum);up.resize(maxNum), down.resize(maxNum), lef.resize(maxNum), rig.resize(maxNum);sc.resize(m), rows.resize(m);for (int i = 0; i <= n; i++){up[i] = i, down[i] = i;lef[i] = i - 1, rig[i] = i + 1;row[i] = 0, col[i] = i, nums[i] = 0;}lef[0] = n, rig[n] = 0, nums[0] = INT_MAX;key = n;for (int i = 0; i <= m; i++)rhead[i] = 0;}void push(int r, int c)//新增坐标在(r,c)的一个节点{row[++key] = r, col[key] = c;up[key] = c, down[key] = down[c];up[down[c]] = key, down[c] = key;if (rhead[r] == 0)rhead[r] = lef[key] = rig[key] = key;else{lef[key] = rhead[r], rig[key] = rig[rhead[r]];lef[rig[rhead[r]]] = key, rig[rhead[r]] = key;}nums[c]++;}vector<vector<int>> getAllAns(){return dfs(false);}vector<int> getAnyAns(){auto v = dfs(true);if (v.size())return v[0];return vector<int>{};}
private:vector<vector<int>> dfs(bool onlyOne){vector<vector<int>>ans;while (true) {if (rig[0] == 0) {rows.resize(rowsid);ans.push_back(rows);rows.resize(m);if (onlyOne)return ans;}int c = min_element(nums.begin() + 1, nums.end()) - nums.begin();if (rig[0] == 0)c = 0;del(c);while (true) {c = down[c];if (c > n)break;reback(col[c]);if (scid == 0)return ans;c = sc[--scid];rowsid--;for (int j = rig[c]; j != c; j = rig[j])reback(col[j]);}sc[scid++] = c;//记录选中idrows[rowsid++] = row[c];for (int j = rig[c]; j != c; j = rig[j])del(col[j]);}return ans;}inline void del(int c)//删除第c列的所有元素和他们所在行的所有元素{lef[rig[c]] = lef[c], rig[lef[c]] = rig[c];for (int i = down[c]; i != c; i = down[i])for (int j = rig[i]; j != i; j = rig[j])down[up[j]] = down[j], up[down[j]] = up[j], nums[col[j]]--;nums[c] = INT_MAX;}inline void reback(int c)//完全回退del操作{lef[rig[c]] = rig[lef[c]] = c, nums[c] = 0;for (int i = down[c]; i != c; i = down[i]) {for (int j = rig[i]; j != i; j = rig[j])down[up[j]] = up[down[j]] = j, nums[col[j]]++;nums[c]++;}}
private:int m, n, key;vector<int>row, col;//每个节点的行，列vector<int>rhead;//每行第一个节点的idvector<int>up, down, lef, rig;//每个节点上下左右的节点idvector<int>nums;//每一列的元素个数vector<int>sc;int scid = 0, rowsid = 0;vector<int>rows;//覆盖选中的行，值的范围是从1到m
};
struct Edge
{int a;//端点idint b;//端点idint dist;
};
class DirectedGraph
{
public://输入有向边集{{1，2}{1，3}{2，3}}，输出邻接表{1:{2,3},2:{3}}static map<int, vector<int>> edgeToAdjaList(const vector<Edge>& v){map<int, vector<int>> ans;for (auto& vi : v) {ans[vi.a].push_back(vi.b);}return ans;}//输入有向带权边集，输出边和权的映射static map<pair<int, int>, int> edgeToValueMap(const vector<Edge>& v){map<pair<int, int>, int>m;for (auto& vi : v) {m[{vi.a, vi.b}] = vi.dist;}return m;}//根据邻接表构建有向图的反向图static map<int, vector<int>> reverseGraph(const map<int, vector<int>>& m){map<int, vector<int>> ans;for (auto& mi : m) {for (auto& k : mi.second)ans[k].push_back(mi.first);}return ans;}//求有向无环图中的最长路径长度，出参nextNode是每个点的后继,len是每个点出发的最长路径长度static int getLongestPath(map<int, vector<int>>& m, map<int, int>& nextNode, map<int, int>& len){int ans = 0;for (auto& ai : m)ans = max(ans, dp(m, nextNode, len, ai.first));return ans;}//判断是否有环static bool hasCircle(int numCourses, map<int, vector<int>>& m){map<int, int>visitt;//单次访问标记map<int, int>flag;//所有访问标记for (int i = 0; i < numCourses; i++){if (flag[i])continue;if (!canFinish(m, i, visitt, flag))return true;}return false;}//拓扑排序BFS版，输入n=3，v={{0,1}{0,2}{1,2}}, 输出{0,1,2}，有环则输出为空static vector<int> topoSort(int n, const vector<Edge>& v){priority_queue<int, vector<int>, greater<int>> q;map<int, int>m;for (auto vi : v)m[vi.b]++;for (int i = 0; i < n; i++)if (m[i] == 0)q.push(i);vector<int>ans;auto mv = edgeToAdjaList(v);while (!q.empty()) {int k = q.top();q.pop();ans.push_back(k);for (auto i : mv[k]) {m[i]--;if (m[i] == 0)q.push(i);}}return ans.size() == n ? ans : vector<int>{};}private:static int dp(map<int, vector<int>>& m, map<int, int>& nextNode, map<int, int>& len, int id){if (len[id])return len[id];len[id] = 1, nextNode[id] = -1; //无后继的则是 - 1for (auto k : m[id]) {if (len[id] < dp(m, nextNode, len, k) + 1) {len[id] = dp(m, nextNode, len, k) + 1;nextNode[id] = k;}}return len[id];}static bool canFinish(map<int, vector<int>>& m, int loc, map<int, int>& visitt, map<int, int>& flag) {if (visitt[loc] == 1)return false;if (flag[loc] == 1)return true;visitt[loc] = 1, flag[loc] = 1;for (int k : m[loc])if (!canFinish(m, k, visitt, flag))return false;visitt[loc] = 0;return true;}
};
class UndirectedGraph
{
public://输入无向边集{{1，2}{1，3}{2，3}}，输出邻接表{1:{2,3},2:{1,3},3:{1,2}}static map<int, vector<int>> undirectedEdgeToAdjaList(vector<Edge>& v){map<int, vector<int>> ans;for (auto& vi : v) {ans[vi.a].push_back(vi.b);ans[vi.b].push_back(vi.a);}return ans;}//输入无向带权边集，输出边和权的映射static map<pair<int, int>, int> undirectedEdgeToValueMap(vector<Edge>& v){map<pair<int, int>, int>m;for (auto& vi : v) {m[{vi.a, vi.b}] = vi.dist;m[{vi.b, vi.a}] = vi.dist;}return m;}//根据无向图的邻接表判断是否有环static bool hasCircle(map<int, vector<int>>m){vector<int>keys; //auto keys = getFirst(m);transform(m.begin(), m.end(), std::back_inserter(keys), [](const pair<int, vector<int>>&p) {return p.first; });int minkey = *min_element(keys.begin(), keys.end());int maxKey = *max_element(keys.begin(), keys.end());Union unions(maxKey - minkey + 1);map<pair<int, int>, int>mp;for (auto& mi : m) {for (auto k : mi.second) {if (mp[make_pair(k, mi.first)])continue;if (unions.inSame(k - minkey, mi.first - minkey))return true;unions.merge(k - minkey, mi.first - minkey);mp[make_pair(mi.first, k)] = 1;}}return false;}//给定一个2n个点的图，选出n条边，刚好覆盖这2n个点static vector<vector<Edge>> getEdgeCover(int n, vector<Edge>& v){DancingLink d(v.size(), n * 2, v.size() * 2);for (int i = 0; i < v.size(); i++) {d.push(i, v[i].a + 1);d.push(i, v[i].b + 1);}vector<vector<Edge>>ans;vector<vector<int>> vrow = d.getAllAns();for (auto vi : vrow) {vector<Edge>vans; //getNumFromId(v, vi)transform(vi.begin(), vi.end(), std::back_inserter(vans), [&](int id) {return v[id]; });ans.push_back(vans);}return ans;}
};
class GridGraph
{
public:vector<int> getNeighbor4(int k)//获得四邻居的id{vector<int>ans;if (k >= col)ans.push_back(k - col);if (k < (row - 1) * col)ans.push_back(k + col);if (k % col)ans.push_back(k - 1);if (k % col < col - 1)ans.push_back(k + 1);return ans;}vector<int> getNeighbor8(int k)//获得八邻居的id{vector<int>ans = getNeighbor4(k);if (k >= col) {if (k % col)ans.push_back(k - col - 1);if (k % col < col - 1)ans.push_back(k - col + 1);}if (k < (row - 1) * col) {if (k % col)ans.push_back(k + col - 1);if (k % col < col - 1)ans.push_back(k + col + 1);}return ans;}int gridCase(vector<vector<int>>& matrix) //示例代码{row = matrix.size();col = matrix[0].size();map<int, vector<int>>m;for (int i = 1; i < matrix.size(); i++)for (int j = 0; j < matrix[0].size(); j++)if (matrix[i][j] == 1 && matrix[i - 1][j] == 1)m[gridId(i, j)].push_back(gridId(i - 1, j));for (int i = 0; i < matrix.size(); i++)for (int j = 1; j < matrix[0].size(); j++)if (matrix[i][j] == 1 && matrix[i][j - 1] == 1)m[gridId(i, j)].push_back(gridId(i, j - 1));int theans = 0;// cal ansreturn theans;}
private:int row;int col;//二维坐标系的邻居偏移量const vector<int> dx4{ 0,0,1,-1 };const vector<int> dy4{ 1,-1,0,0 };const vector<int> dx8{ 0,0,1,-1,1,1,-1,-1 };const vector<int> dy8{ 1,-1,0,0 ,1,-1,1,-1 };//一维id坐标系的邻居偏移量vector<int> d4, d8;void InitD4D8() //计算d4和d8，先给col赋值再调用{d4 = { 1,-1,col,-col }, d8 = { 1,-1,col,-col, col + 1,col - 1,-col + 1,-col - 1 };}int gridId(int x, int y) //阅读顺序的id,先给col赋值再调用{return x * col + y;}
};
class GrapgOpt
{
public://根据点集取子图static map<int, vector<int>> getSubGraph(map<int, vector<int>>& m, vector<int>& v){map<int, vector<int>>ans;map<int, int>mv;for (auto vi : v)mv[vi] = 1;for (auto vi : v) {for (auto mi : m[vi]) {if (mv[mi])ans[vi].push_back(mi);}}return ans;}
};
class SemiConnect
{
public://半连通分量分割static vector<vector<int>> semiConnectComponent(map<int, vector<int>>& m){vector<vector<int>>allans;map<int, int>visit;for (auto& mi : m) {int k = mi.first;if (visit[k])continue;vector<int>ans;DFS(m, visit, k, ans);allans.push_back(ans);}return allans;}
protected://DFS从k开始遍历，记录所有节点最后一次访问的顺序的反序static void DFS(map<int, vector<int>>& m, map<int, int>& visit, int k, vector<int>& ans){if (visit[k])return;visit[k] = 1;for (auto i : m[k])DFS(m, visit, i, ans);ans.insert(ans.begin(), k);}
};
class KosarajuStrongConnect :public DirectedGraph, public GrapgOpt, public SemiConnect
{
public://Kosaraju算法，强连通分量分割static vector<vector<int>> connectComponent(map<int, vector<int>>& m){vector<vector<int>> semi = semiConnectComponent(m);auto m2 = reverseGraph(m);vector<vector<int>>allans;map<int, int>visit;for (auto& s : semi) {auto m3 = getSubGraph(m2, s);for (auto& k : s) {if (visit[k])continue;vector<int>ans;DFS(m3, visit, k, ans);allans.push_back(ans);}}return allans;}
};
class TarjanDoubledirect
{
public:vector<pair<int, int>>cutb;//割边vector<int>cutv;//割点vector<vector<int>>conv;//点双连通分量的点集vector<vector<long long>>convb;//点双连通分量的边集int cons = 0;//无向连通分量数目TarjanDoubledirect(int n, map<int, vector<int>>& m){this->n = n;this->m = m;visit.resize(n);added.resize(n);dfn.resize(n);low.resize(n);for (int i = 0; i < n; i++)if (!visit[i]) {root = i;dfs(i);cons++;}FillConv();}
private:void dfs(int k){visit[k] = true;low[k] = dfn[k] = dfnId++;bool cv = false;int chNum = 0;st.push(k);for (auto nk : m[k]) {if (isBackB(nk))low[k] = min(low[k], dfn[nk]);if (visit[nk])continue;chNum++;sFa.push(k);dfs(nk);sFa.pop();low[k] = min(low[k], low[nk]);vector<int>conv1;vector<long long>convb1;if (low[nk] >= dfn[k]) {cv = true;for (int time = INT_MAX; time; time--) {if (st.top() == nk)time = 1;conv1.push_back(st.top());added[st.top()] = true;for (auto i : m[st.top()])if (!added[i])convb1.push_back((long long)(st.top()) * n + i);st.pop();}if (conv1.size() > 1) {conv1.push_back(k);conv.push_back(conv1);convb.push_back(convb1);}}if (low[nk] >= dfn[nk])cutb.push_back(make_pair(k, nk));}if ((k != root && cv && chNum > 0) || (k == root && chNum > 1))cutv.push_back(k);}bool isBackB(int nk) // 判断从k到nk是不是后向边{return visit[nk] && (sFa.empty() || nk != sFa.top());//如果st.top()是nk，则是树边，不是后向边}void FillConv()//补充由单点组成的点连通分量{map<int, int>m;for (auto& ci : conv) {for (auto& k : ci)m[k] = 1;}vector<int>conv1(1);for (int i = 0; i < n; i++)if (m[i] == 0) {conv1[0] = i;conv.push_back(conv1);convb.push_back(vector<long long>());}}int n;int dfnId = 0;int root;vector<bool>visit;//DFS访问标记vector<bool>added;vector<int>dfn;//首次访问的次序vector<int>low;//通过一条后向边能达到的最小dfnmap<int, vector<int>> m;//邻接表stack<int>sFa;//用于判断父节点stack<int>st;
};
class TarjanStrongConnect
{
public:vector<vector<int>>conv;//强连通分量的点集TarjanStrongConnect(int n, map<int, vector<int>>& m){this->n = n;this->m = m;visit.resize(n);added.resize(n);dfn.resize(n);low.resize(n);for (int i = 0; i < n; i++)if (!visit[i]) {root = i;dfs(i);}FillConv();}
private:void dfs(int k){visit[k] = true;low[k] = dfn[k] = dfnId++;bool cv = false;int chNum = 0;st.push(k);for (auto nk : m[k]) {if (isBackB(nk))low[k] = min(low[k], dfn[nk]);if (visit[nk])continue;chNum++;dfs(nk);low[k] = min(low[k], low[nk]);}vector<int>conv1;vector<long long>convb1;if (low[k] >= dfn[k]) {cv = true;for (int time = INT_MAX; time; time--) {if (st.top() == k)time = 1;conv1.push_back(st.top());added[st.top()] = true;st.pop();}conv.push_back(conv1);}}bool isBackB(int nk) // 判断从k到nk是不是后向边{return visit[nk] && !added[nk];}void FillConv()//补充由单点组成的点连通分量{map<int, int>m;for (auto& ci : conv) {for (auto& k : ci)m[k] = 1;}vector<int>conv1(1);for (int i = 0; i < n; i++)if (m[i] == 0) {conv1[0] = i;conv.push_back(conv1);}}int n;int dfnId = 0;int root;vector<bool>visit;//DFS访问标记vector<bool>added;vector<int>dfn;//首次访问的次序vector<int>low;//通过一条后向边能达到的最小dfnmap<int, vector<int>> m;//邻接表stack<int>st;
};
class Dijskra
{
public:map<int, int>dis;Dijskra(map<int, vector<int>>& m, map<pair<int, int>, int>& value, int n, int start){for (int i = 0; i < n; i++)dis[i] = INT_MAX;que.push({ start,0 });dis[start] = 0;while (!que.empty()){Node nod = que.top();que.pop();if (visit[nod.id])continue;visit[nod.id] = 1;for (auto& vi : m[nod.id]) {if (nod.len + value[{nod.id, vi}] < dis[vi]) {que.push({ vi, dis[vi] = nod.len + value[{nod.id, vi}] });}}}}
private:struct Node{int id;int len;};class cmp{public:bool operator()(Node a, Node b){return a.len > b.len;}};priority_queue< Node, vector< Node>, cmp>que;map<int, int>visit;
};
class Kruskal
{
public://计算最小生成树，结果按照边从小到大排序,出参treeNum是森林中树的数量vector<Edge> minCostConnectPoints(int n, vector<Edge>& v, int& treeNum){sort(v.begin(), v.end(), cmp);Union unions(n);vector<Edge>ans;for (int i = 0, j = 0; j < n - 1 && i < v.size(); i++){if (unions.inSame(v[i].a, v[i].b))continue;unions.merge(v[i].a, v[i].b);ans.push_back(v[i]);j++;}treeNum = unions.getRootNums();return ans;}
private:static bool cmp(Edge& a, Edge& b){return a.dist < b.dist;}
};
class Prim
{
public://计算最小生成树，结果按照边从小到大排序static vector<pair<int, int>> minCostConnectPoints(int n, map<pair<int, int>, int>& value){vector<bool>visit_(n);vector<int>minLen(n);for (int i = 0; i < n; i++) {minLen[i] = INT_MAX;visit_[i] = false;}minLen[getStartId(n, value)] = INT_MIN;vector<pair<int, int>>ans;for (int i = 0; i < n; i++) {int id = getId(n, visit_, minLen);for (int j = 0; j < n; j++) {if (visit_[j] && value[make_pair(id, j)] == minLen[id]) {ans.push_back(make_pair(id, j));break;}}visit_[id] = true;fresh(n, visit_, minLen, value, id);}return ans;}
private:static int getStartId(int n, map<pair<int, int>, int>& value){int m = INT_MAX;int ans = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i != j && m > value[make_pair(i, j)]) {m = value[make_pair(i, j)];ans = i;}}}return ans;}static int getId(int n, vector<bool>& visit_, vector<int>& minLen){int m = INT_MAX;int ans = 0;for (int i = 0; i < n; i++) {if (!visit_[i] && m > minLen[i]) {m = minLen[i];ans = i;}}return ans;}static void fresh(int n, vector<bool>& visit_, vector<int>& minLen, map<pair<int, int>, int>& value, int id){for (int i = 0; i < n; i++) {if (!visit_[i])minLen[i] = min(minLen[i], value[make_pair(i, id)]);}}
};
class Hierholzer {
public:stack<int>euler;//欧拉回路或链路,栈顶是起点Hierholzer(int n, map<int, vector<int>>& m, int type, int start = 0)//type=0是无向图 1是有向图{this->n = n;this->m = m;this->type = type;dfs(GetStartPoint(start));}
private:int GetStartPoint(int start)//链路是唯一起点，回路是指定起点{if (type == 0) {for (auto& mi : m) {if (mi.second.size() % 2)return mi.first;for (auto nk : mi.second)num[id(mi.first, nk)]++;}for (auto& ni : num)ni.second /= 2;}else {map<int, int>m2;for (auto& mi : m)for (auto nk : mi.second)m2[nk]++, num[id(mi.first, nk)]++;for (auto& mi : m)if (mi.second.size() > m2[mi.first])return mi.first;}return start;}void dfs(int k){while (true) {while (mid[k] < m[k].size()) {if (num[id(k, m[k][mid[k]])]-- <= 0)mid[k]++;else sdfs.push(k), k = m[k][mid[k]];}euler.push(k);if (sdfs.empty()) return;k = sdfs.top(), sdfs.pop();}}inline long long id(int a, int b){if (type == 0 && a > b)a ^= b ^= a ^= b;return (long long)a * n + b;}int n;int type;stack<int>sdfs;map<int, vector<int>> m;//邻接表map<int, int>mid;map<long long, int>num;//支持多重边
};
class Hamilton
{
public:stack<int> hami;//哈密顿链路Hamilton(int n, map<int, vector<int>>& m, int type)//type=0是无向图 1是有向图{this->n = n;this->m = m;this->type = type;for (int i = 0; i < n; i++)dfs(i);}
private:bool dfs(int k){s.push(k);if (s.size() == n) {hami = s;return true;}for (auto nk : m[k]) {if (visit[k])continue;visit[k] = 1;if (dfs(nk))return true;visit[k] = 0;}s.pop();return false;}int n;int type;map<int, vector<int>> m;//邻接表map<int, int>visit;stack<int>s;
};
class ReBuild
{
public:stack<int> ans;ReBuild(map<int, int>& dis, map<int, vector<int>>& m, int col, int s, int e){this->e = e;this->col = col;ans.push(e);dfs(dis, m, s);}
private:bool dfs(map<int, int>& dis, map<int, vector<int>>& m, int k){if (k == e)return true;for (int nex : m[k]) {if (dis[nex] == dis[k] + len(k, nex) && dfs(dis, m, nex)) {ans.push(k);return true;}}return false;}int len(int s, int e){if (s / col == e / col)return abs(s - e);return abs(s - e) / col;}int col;int e;
};

三，test

测试代码还比较拉垮，先测试编译问题。

void test1()
{cout << MultiMulti(2, 10);//输出1024NumberTheory{};Sieve::GetSingleA();Facs{};Phi{};Order{};BSGS{};
}
void test2()
{DirectedGraph{};UndirectedGraph{};GridGraph{};GrapgOpt{};SemiConnect{};KosarajuStrongConnect{};int n=1;map<int, vector<int>> m;TarjanDoubledirect{ n,m };TarjanStrongConnect{ n,m };map<pair<int, int>, int> value;Dijskra{ m,value ,n,0 };Kruskal{};Prim{};Hierholzer{n,m,0,0};Hamilton{ n,m,0 };map<int, int> dis;ReBuild{dis,m,0,0,0};
}
int main()
{test1();test2();return 0;
}