ACM模板（数学算法）
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
目录
〇全文说明、基础代码
所有接口分三类
- 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中有多少十进制数里面有数字9n<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 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//输入有向边集{{12}{13}{23}}输出邻接表{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=3v={{0,1}{0,2}{1,2}}, 输出{0,1,2}有环则输出为空
///2.4无向图///
#define UndirectedEdgeToAdjaList UndirectedGraph::undirectedEdgeToAdjaList//输入无向边集{{12}{13}{23}}输出邻接表{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=245
static 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;
}
//一个十进制数里面有没有数字9
static bool isHas9(int n)
{
while (n) {
if (n % 10 == 9)return true;
n /= 10;
}
return false;
}
//1-n中有多少十进制数里面有数字9n<10^9
static 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) {
ans2 = ans;
int p = vi.first, k = vi.second;
while (k--) {
Fcheng(ans, p);
ans2 = Join(ans2, ans);
}
ans = ans2;
}
return ans;
}
};
class Phi :public Facs, public Basic
{
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)并获取phi(n)的所有因子facs
static int getFacsOfPhi(int n, vector<int>&facs)
{
vector<pair<int, int>> vp = fenjie(n);
vector<int>v;
for (auto vi : vp) {
v.push_back(vi.first);
if (vi.second > 1)facs.push_back(vi.first);
facs = getInAnyData(facs, getFacs(vi.first - 1));
}
return getPhiWithFacs(n, getFacs(n));
}
private:
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;//记录选中id
rows[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;//每行第一个节点的id
vector<int>up, down, lef, rig;//每个节点上下左右的节点id
vector<int>nums;//每一列的元素个数
vector<int>sc;
int scid = 0, rowsid = 0;
vector<int>rows;//覆盖选中的行值的范围是从1到m
};
struct Edge
{
int a;//端点id
int b;//端点id
int dist;
};
class DirectedGraph
{
public:
//输入有向边集{{12}{13}{23}}输出邻接表{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=3v={{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; //无后继的则是 - 1
for (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 Basic
{
public:
//输入无向边集{{12}{13}{23}}输出邻接表{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)
{
auto keys = getFirst(m);
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)ans.push_back(getNumFromId(v, vi));
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 ans
return 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 SemiConnect, public DirectedGraph, public GrapgOpt
{
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;//通过一条后向边能达到的最小dfn
map<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;//通过一条后向边能达到的最小dfn
map<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
{
//计算最小生成树结果按照边从小到大排序
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;
};