[数据结构与算法]基础ds算法模板

from AcWing

基础算法

归并排序

void merge_sort(int q[], int l, int r){
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

二分算法

int型：
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点型：
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r){
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps){
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B){
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ ){
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

前缀和

一维：
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
二维：
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

差分

一维：
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
二维：
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

位运算

求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

尺取法

void solve(){
	int res = n+1;
	int be=0,ed=0,sum=0;
	for( ; ; ){
		while(ed<n && sum<s){
			sum += a[ed++];
		}
		if(sum < s) break;
		res = min(res,ed-be);
		sum -= a[be++];
	}
} 

三角形边problem

// 分析极限条件，即两边之和等于第三边的情况
    p: 三角形第三条边
    i：1~n 读入 num[i]
    long long  sum = 0;
    sort(num+1, num+n+1);
    int x, y;
    for(int i  = 1; i <= n; i++)
    {
        x = lower_bound(num+i+1, num+n+1, p+num[i]) - (num+i+1);      // 大于等于
        y = upper_bound(num+i+1, num+n+1, abs(num[i]-p)) - (num+i+1);  // 大于
        sum += x-y;
    }
    cout << sum;

约瑟夫环

int circle(int n, int m){	int ans;	for(int i=2; i <= n; i++){		ans = (ans + m)%i;	}	return ans+1;} 

最长上升子序列（LIS）

//序列(1, 7, 3, 5, 9, 4, 8) ，其最长上升子序列长度为4，其中一条LIS(1,3,5,8)
//核心代码1
const int MAXN;
int a[MAXN]
int low[MAXN];
int main(){
    int n;
    cin >> n;
    memset(low,0x3f,sizeof low);
    for(int i=0;i<n;i++)
        cin >> a[i];
    low[1] = a[1];
    int num = 1;
    for(int i=1;i<n;i++){
        if(a[i] > low[num])
            low[++num] = a[i];
        else
            二分查找
            low[ ] = a[i];
    }
    cout << num;
    return 0;
}

离散化

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}


顺序无所谓的简单离散化
    
unordered_map<int, int> S;
int get(int x)
{
    if (S.count(x) == 0) S[x] = ++ n;
    return S[x];
}

/*
struct Query{
    int x, y, e;
}query[N];

for (int i = 0; i < m; i ++ ){
	int x, y, e;
    scanf("%d%d%d", &x, &y, &e);
    query[i] = {get(x), get(y), e};
}
*/     

数据结构

并查集

(1)朴素并查集：
    int p[N]; //存储每个点的祖宗节点
    // 返回x的祖宗节点
    int find(int x){
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);

(2)维护size的并查集：
    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
    // 返回x的祖宗节点
    int find(int x){
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ){
        p[i] = i;
        size[i] = 1;
    }
    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

(3)维护到祖宗节点距离的并查集：
    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
    // 返回x的祖宗节点
    int find(int x){
        if (p[x] != x){
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }
    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ){
        p[i] = i;
        d[i] = 0;
    }
    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

哈希

(1) 拉链法
    int h[N], e[N], ne[N], idx;
    // 向哈希表中插入一个数
    void insert(int x){
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }
    // 在哈希表中查询某个数是否存在
    bool find(int x){
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;
        return false;
    }
(2) 开放寻址法
    int h[N];
    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x){
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x){
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }
(3) 字符串哈希
    核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

单调栈

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ ){
    while (tt && check(stk[tt], i)) tt--;
    stk[ ++ tt] = i;
}

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 ?1
 	cin >> m;
    while(m --)
    {
        int x;
        cin >> x;
        while(tt && stk[tt] >= x) tt --;
        if(tt) cout << stk[tt] << ' ';
        else cout << "-1" << ' ';
        
        stk[ ++ tt] = x;
    }

单调队列

确定滑动窗口位于每个位置时，窗口中的最大值和最小值
cin >> n >> k;
for(int i = 0; i < n; i ++) cin >> a[i];

int hh = 0, tt = -1;
for(int i = 0; i < n; i ++){
	if(hh <= tt && i - k + 1 > q[hh]) hh ++;
    while(hh <= tt && a[q[tt]] >= a[i]) tt --;
    q[ ++ tt] = i;
    if(i >= k - 1) cout << a[q[hh]] << ' '; 
    }   
puts("");

hh = 0, tt = -1;
for(int i = 0; i < n; i ++){
    if(hh <= tt && i - k + 1 > q[hh]) hh ++;
    while(hh <= tt && a[q[tt]] <= a[i]) tt --;
    q[++ tt] = i;
    if(i >= k - 1) cout << a[q[hh]] << ' ';
    }
puts("");

Trie树

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str){
    int p = 0;
    for (int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}
// 查询字符串出现的次数
int query(char *str){
    int p = 0;
    for (int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

对顶堆（动态中位数）

priority_queue<int> down;
priority_queue<int, vector<int>, greater<int>> up;
 
int x;
scanf("%d", &x);
if (down.empty() || x <= down.top()) down.push(x);
else up.push(x);

if (down.size() > up.size() + 1) up.push(down.top()), down.pop();
if (up.size() > down.size()) down.push(up.top()), up.pop();

哈夫曼树

// 模板1
struct node{
Elem data;
node *lc,*rc;
};
bool operator < (node *a,node *b){//a<b 排序方式
//...
}
priority_queue<*node> pq;

void merge(){
	while( pq.size()>1 ){
	node *now=newNode();
	now->lc=pq.top();
	pq.pop();
	now->rc=pq.top();
	pq.pop();
	now->data=calc( now->lc->data , now->rc->data );
	//calc(a,b) 表示将这两棵树合并后，新的值；哈夫曼树一般是 a+b
	pq.push(now);
	}
}
// 模板2
priority_queue<int,vector<int>,greater<int> > p;
for(int i=0;i<n;i++){
		int x;
		cin >> x;
		p.push(x);
	}
	while(1){
		int x,y,c;
		x = p.top();
		p.pop();
		y = p.top();
		p.pop();
		c = (x+y);
		sum += c;
		p.push(c);
		if(p.size()==1) break;
	}

STL

vector, 变长数组，倍增的思想
    size() 返回元素个数        empty() 返回是否为空    clear() 清空      front()/back()
    push_back()/pop_back()   begin()/end()        []  支持比较运算，按字典序

pair<int, int>
    first, 第一个元素     second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length() 返回字符串长度            empty()              clear()
    substr(起始下标，(子串长度))  返回子串      c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()       empty()      push()  向队尾插入一个元素       front()  返回队头元素
    back()  返回队尾元素      pop()  弹出队头元素

stack, 栈
    size()      empty()      push()  向栈顶插入一个元素
    top()  返回栈顶元素        pop()  弹出栈顶元素

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()       empty()        clear()         begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)
    
    set/multiset
        insert()  插入一个数       find()  查找一个数       count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap   哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []
    count()  返回有多少个1    any()  判断是否至少有一个1      none()  判断是否全为0
    set()  把所有位置成1      set(k, v)  将第k位变成v       reset()  把所有位变成0
    flip()  等价于~          flip(k) 把第k位取反

priority_queue, 优先队列，默认是大根堆
    size()    empty()    push()  插入一个元素    top()  返回堆顶元素    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
plus.
     make_heap()      生成一个堆，大顶堆或小顶堆   
     push_heap()      向堆中插入一个元素，并且使堆的规则依然成立
     pop_heap()       是在堆的基础上，弹出堆顶元素
commun use：
    for(int i=1;i<=n;i++){
        cin >> h[i];
        push_heap(h+1,h+1+i,greater<int>());
    }   //让数组h的元素以小根堆的顺序存储

    // define cmp function
    auto cmp = [](const int x, const int y) { return x > y;};
    vector<int> nums2 = {40, 50, 10, 30, 20};
    // generate heap in the range of numsector（在numsector范围内生成堆）
    make_heap(nums2.begin(), nums2.end(), cmp);
    cout << "initial max value : " << nums2.front() << endl;
    // pop max value
    pop_heap(nums2.begin(), nums2.end(), cmp);
    nums.pop_back();
    cout << "after pop, the max vsalue : " << nums2.front() << endl;
    // push a new value
    nums2.push_back(0);
    push_heap(nums2.begin(), nums2.end(), cmp);
    cout << "after push, the max value : " << nums2.front() << endl;

    ps.若要大根堆的形式，则不需要创建 cmp

map  关联容器，提供一对一的hash
    key － value
    // 定义一个map对象
	map<int, string> mp;
 	// 第一种 用insert函數插入pair
	mp.insert(pair<int, string>(000, "student_zero"));
	// 第二种 用insert函数插入value_type数据
	mp.insert(map<int, string>::value_type(001, "student_one"));
 	// 第三种 用"array"方式插入
	mp[123] = "student_first";
	mp[456] = "student_second";
                                        // 题目一般要构造 map<string,int> mp;
————————————————————————————————————————————————————
	// find 返回迭代器指向当前查找元素的位置否则返回map::end()位置
    iter = mp.find(11);   // ？"11" 
    if(iter != mp.end())
           cout<<"Find, the value is" << iter->second << endl;
	else   cout<<"Do not Find"<<endl;
————————————————————————————————————————————————————
	//迭代器刪除
    iter = mp.find("123");
    mp.erase(iter);
 	//用关键字刪除
	int n = mp.erase("123"); //如果刪除了會返回1，否則返回0
	//用迭代器范围刪除 : 把整个map清空
    mp.erase(mp.begin(), mp.end());
    //等同于mp.clear()
————————————————————————————————————————————————————
    //遍历输出
	map<int, string>::iterator iter;
	map<int, string>::reverse_iterator iter;          //反向迭代器
    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++){ 
        cout<<iter->first<<' '<<iter->second<<endl;  
     }  
    
    int nSize = mp.size(); 
    //此处应注意，应该是 for(int nindex = 1; nindex <= nSize; nindex++)  
    //而不是 for(int nindex = 0; nindex < nSize; nindex++)  
    for(int nindex = 1; nindex <= nSize; nindex++){
        cout<<mp[nindex]<<endl; 
	}
————————————————————————————————————————————————————
    iter = mapStudent.lower_bound(1);  //返回的是下界1的迭代器  
    cout<<iter->second<<endl;  
    lower_bound函数用法，这个函数用来返回要查找关键字的下界(是一个迭代器)
    upper_bound函数用法，这个函数用来返回要查找关键字的上界(是一个迭代器)
    例如：map中已经插入了1，2，3，4的话，如果lower_bound(2)，返回2，而upper-bound（2），返回3
————————————————————————————————————————————————————
    swap()           交换两个map

set 
    set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一，而且系统能根据元素的值 自动进行排序
    插入删除效率高
————————————————————————————————————————————————————
    set<int> s;
    set<int>::iterator iter;
    for(int i = 1 ; i <= 5; ++i){
         s.insert(i);
     }
     for(iter = s.begin() ; iter != s.end() ; ++iter){
        cout<<*iter<<" ";
     }
     pair<set<int>::const_iterator,set<int>::const_iterator> pr;
     pr = s.equal_range(3);
     cout<<"第一个大于等于 3 的数是 ："<<*pr.first<<endl;
     cout<<"第一个大于 3的数是 ： "<<*pr.second<<endl;
————————————————————————————————————————————————————
     int a[] = {1,2,3};
     set<int> s;
     set<int>::iterator iter;
     s.insert(a,a+3);
     for(iter = s.begin() ; iter != s.end() ; ++iter){
         cout<<*iter<<" ";
     }
     cout<<endl;
     pair<set<int>::iterator,bool> pr;
     pr = s.insert(5);
     if(pr.second){
         cout<<*pr.first<<endl;
     }
————————————————————————————————————————————————————
     set<int> s;
     s.insert(1);
     s.insert(3);
     s.insert(4);
     cout<<*s.lower_bound(2)<<endl;
     cout<<*s.lower_bound(3)<<endl;
     cout<<*s.upper_bound(3)<<endl;
   // ps. multiset

树

近似满二叉树

Elem data[maxn];
int lc(int pos) { return 2*pos; }//pos<<1
int rc(int pos) { return 2*pos+1; }//pos<<1|1

void preorder(int root){
	work(root);
	preorder(lc(root));//preorder(root<<1)
	preorder(rc(root));//preorder(root<<1|1)
}
void postorder(int root){
	preorder(lc(root));//preorder(root<<1)
	preorder(rc(root));//preorder(root<<1|1)
	work(root);
}
void inorder(int root){
	preorder(lc(root));//preorder(root<<1)
	work(root);
	preorder(rc(root));//preorder(root<<1|1)
}

树的储存与遍历

//孩子表示法
struct node{
//data
	int child[maxn];//各个孩子的地址
	int cntchild;
}n[maxn];
void preorder(int root){
	work(root);//work() 代指操作，例如输出、计算或什么都不做，下同
	for(int i=0;i<n[root].cntchild;i++)
	preorder(n[root].child[i]);
}
void postorder(int root){
	for(int i=0;i<n[root].cntchild;i++)
	preorder(n[root].child[i]);
	work(root);
}
void inorder(int root){
	if(n[root].cntchild)
	inorder(n[root].child[0]);
	work(root);
	for(int i=1;i<n[root].cntchild;i++)
	inorder(n[root].child[i]);
}
void bfs(int root){//层序遍历
	queue<int> q;
	q.push(root);
	while( q.size() ){
	int now=q.front();
	q.pop();
	for(int i=0;i<n[now].cntchild;i++)
	q.push(n[now].child[i]);
	work(now);
}
}

//儿子兄弟表示法，主要用于前后序遍历
struct node{
	//data
	int child,bro;
}n[maxn];
void preorder(int root){
	work(root);
	preorder(n[root].child);
	preorder(n[root].bro);
}
void postorder(int root){
	postorder(n[root].child);
	work(root);
	postorder(n[root].bro);
}

//图表示法，主要用于从特定点遍历
vector<int> Edg[maxn];
int pa[maxn];
void addEdge(int u,int v){
	Edg[u].push(v);
	Edg[v].push(u);
}
void dfs(int root,int fa){
	pa[root]=fa;
	for(auto to : Edg[root])
	if(to!=fa)
	dfs(to,root);
	work(root);
}
//dfs(u,-1)
void bfs(int root){
	pa[root]=-1;
	queue<int> q;
	q.push(root);
	while( q.size() ){
		int now=q.front();
		q.pop();
		for(auto to : Edg[now])
		if(to!=pa[now]){
		q.push(to);
		pa[to]=now;
		}
	work(now);
	}
}

树的遍历

DLR–前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）

LDR–中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）

LRD–后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）

typedef struct TreeNode
{
    int data;
    TreeNode * left;
    TreeNode * right;
    TreeNode * parent;
}TreeNode;
 
void pre_order(TreeNode * Node)//前序遍历递归算法
{
    if(Node == NULL)
        return;
    printf("%d ", Node->data);//显示节点数据，可以更改为其他操作。在前面
    pre_order(Node->left);
    pre_order(Node->right);
}
void middle_order(TreeNode *Node)//中序遍历递归算法
{
    if(Node == NULL)
        return;
    middle_order(Node->left);
    printf("%d ", Node->data);//在中间
    middle_order(Node->right);
}
void post_order(TreeNode *Node)//后序遍历递归算法
{
    if(Node == NULL)
        return; 
    post_order(Node->left);
    post_order(Node->right);
    printf("%d ", Node->data);//在最后
}

//层序遍历
void FloorPrint(pTreeNode Tree)  //层序遍历
{
    pTreeNode temp[100];   //创建pTreeNode指针类型的指针数组
    int in = 0;
    int out = 0;
    temp[in++] = Tree;  //先保存二叉树根节点 
    while (in > out){
        if (temp[out]){
            cout << temp[out]->data << " → ";
            temp[in++] = temp[out]->leftPtr;
            temp[in++] = temp[out]->rightPtr;
        }
        out++;
    }
}

搜索与图论

深度优先遍历

int dfs(int u){
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

宽度优先遍历

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size()){
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i]){
        int j = e[i];
        if (!st[j]){
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

拓扑排序

bool topsort(){
    int hh = 0, tt = -1;
    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;
    while (hh <= tt){
        int t = q[hh ++ ];
        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }
    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

int main(){
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        cin >> a >> b;
        add(a,b);
        d[b]++;
    }
    if(!topsort()) puts("-1");
    else 输出拓扑排序的数组p[]
}

朴素dijkstra

时间复杂是 O(n2+m), n 表示点数，m 表示边数

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510;
int n,m;
int g[N][N];      // 稠密图用领接矩阵存储比较省空间
int dist[N];      //dist[i] i结点到起始点（1号结点）的距离
bool st[N];       //st[i] 用于标记i结点的最短路径是否确定，若确定st[i]=true

int dijkstra(){
    memset(dist,0x3f,sizeof dist); 
    dist[1] = 0;
    for(int i=0;i<n-1;i++){        //n次迭代，每次寻找不在s中距离最近的点t
        int t=-1;         //便于更新第一个点
        //将t设置为-1 因为Dijkstra算法适用于不存在负权边的图
        for(int j=1;j<=n;j++)    
            if(!st[j]&&(t==-1 || dist[t]>dist[j]))
            //该步骤即寻找还未确定最短路的点中路径最短的点
                t = j;     
        for(int j=1;j<=n;j++)
            dist[j] = min(dist[j],dist[t] + g[t][j]);
        st[t]=true;       //将t加到s中
    }
    if(dist[n]==0x3f3f3f3f) return -1;    //路径不存在
    return dist[n];
}
int main(){
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);
     //邻接矩阵的初始化，由于求的是最小值，因此初始为无穷大
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b],c);    //重边  取最小值
    }
    printf("%d\n",dijkstra());
    return 0;
}

/*
如果是问编号a到b的最短距离该怎么改呢? 
回答： 初始化时将 dist[a]=0,以及返回时return dist[b]。
*/

堆优化dijkstra

时间复杂度 O(mlogn), n 表示点数，m 表示边数

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
const int N = 1000010;
int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    priority_queue<pii, vector<pii>,greater<pii>> heap; 
    heap.push({0,1});       // first存储距离，second存储节点编号
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        int distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j = e[i];
            if(dist[j] > dist[ver] + w[i]){
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    cout << dijkstra() << endl;
    return 0;
}

Bellman-Ford算法

时间复杂度 O(nm), n 表示点数，m 表示边数

有边数限制的最短路 边权可能为负数 图中可能 存在负权回路

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510, M = 10010;
struct Edge{
    int a,b,c;
}edges[M];
int n,m,k;
int dist[N];     // dist[x]存储1到x的最短路距离
int last[N];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
void bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
 // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for(int i=0;i<k;i++){
        memcpy(last,dist,sizeof dist);
        for(int j=0;j<m;j++){
            auto e = edges[j];
            dist[e.b] = min(dist[e.b],last[e.a]+e.c);
        }
    }
}
int main(){
    cin >> n >> m >> k;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        edges[i] = {a,b,c};
    }
    bellman_ford();
    if(dist[n] > 0x3f3f3f3f/2)    puts("impossible");
    else
        cout << dist[n] << endl;
    return 0;
}

spfa 算法（队列优化的Bellman-Ford算法）

时间复杂度 平均情况下 O(m)，最坏情况下 O(nm) , n 表示点数，m 表示边数 1≤n,m≤105

图中可能存在重边和自环， 边权可能为负数 数据保证不存在负权回路

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    while (q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
//从队列中取出来之后该节点st被标记为false,代表之后该节点如果发生更新可再次入队
        for (int i = h[t]; i != -1; i = ne[i])       {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])            {
                dist[j] = dist[t] + w[i];
//当前已经加入队列的结点，无需再次加入队列，即便发生了更新也只用更新数值即可，重复添加降低效率                
                if (!st[j]){   // 如果队列中已存在j，则不需要将j重复插入
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}
int main(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    int t = spfa();
    if (t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);
    return 0;
}

spfa判断图中是否存在负环

时间复杂度是 O(nm), n 表示点数，m 表示边数

可能存在重边和自环， 边权可能为负数。 判断图中是否存在负权回路。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
//统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于n，则说明存在环
const int N = 2010, M = 10010;
int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];
void add(int a, int b, int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}
// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
//    memset(dist, 0x3f, sizeof dist);
//    dist[1] = 0;
    queue<int> q;
    for(int i=1;i<=n;i++){
        st[i] = true;
        q.push(i);
    }
    while (q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                // 如果超过了n-1 根据抽屉原理，说明经过某个节点两次，则说明有环
                if (cnt[j] >= n) return true;
                if (!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
     if(spfa()) cout << "Yes";
     else cout << "No";
    return 0;
}

在原图的基础上新建一个虚拟源点，从该点向其他所有点连一条权值为0的有向边。那么原图有负环等价于新图有负环。此时在新图上做spfa，将虚拟源点加入队列中。然后进行spfa的第一次迭代，这时会将所有点的距离更新并将所有点插入队列中。

dist[x] 记录虚拟源点到x的最短距离
cnt[x] 记录当前x点到虚拟源点最短路的边数，初始每个点到虚拟源点的距离为0，
只要他能再走n步，即cnt[x] >= n，则表示该图中一定存在负环
由于从虚拟源点到x至少经过n条边时，则说明图中至少有n + 1个点，表示一定有点是重复使用.

若dist[j] > dist[t] + w[i],则表示从t点走到j点能够让权值变少，因此进行对该点j进行更新，并且对应cnt[j] = cnt[t] + 1,往前走一步

注意：该题是判断是否存在负环，并非判断是否存在从1开始的负环，因此需要将所有的点都加入队列中，更新周围的点

floyd算法

时间复杂度是 O(n3), n 表示点数

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 210, inf = 1e9;
int n,m,Q;
int d[N][N];
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd(){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}

int main(){
    cin >> n >> m >> Q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) d[i][j] = 0;
            else d[i][j] = inf;
            
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b],c);
    }    
    floyd();    
    while(Q--){
        int a,b;
        cin >> a >> b;
        int t = d[a][b];
        if(t > inf/2) puts("impossible");
        else cout << t << endl;
    }
    return 0;
}

朴素版prim算法

时间复杂度是 O(n^2 +m), n表示点数，m 表示边数

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510, inf=0x3f3f3f3f;
int n,m;
int g[N][N];   // 邻接矩阵，存储所有边
int dist[N];   // 存储其他点到当前最小生成树的距离
bool st[N];    // 存储每个点是否已经在生成树中
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim(){
    memset(dist,0x3f,sizeof dist);
    int res = 0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j] && (t==-1 || dist[t] > dist[j]))
            t = j;
        if(i && dist[t]==inf) return inf;
        if(i) res += dist[t];
        st[t] = true;
        for(int j=1;j<=n;j++) dist[j] = min(dist[j],g[t][j]);
    }
    return res;
}

int main(){
    cin >> n >> m;
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b],c);
    }
    int t = prim();
    if(t == inf) puts("impossible");
    else cout << t << endl;
    return 0;
}

kruskal算法

时间复杂度是 O(mlogm), n 表示点数，m 表示边数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 200010, INF = 0x3f3f3f3f;
int n, m;
int p[N];
struct Edge{
	int a, b, w;	
	bool operator < (const Edge & W) const
	{
		return w <W.w;
	}
}edges[M];

int find(int x){
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}


int kruskal(){
	sort(edges, edges + m);	
	for(int i = 1; i <= n; i ++) p[i] = i;
	
	int res = 0, cnt = 0;
	for(int i = 0; i < m; i ++){
		int a = edges[i].a, b = edges[i].b, w = edges[i].w;		
		a = find(a), b = find(b);
		if(a != b){
			p[a] = b;
			res += w;
			cnt ++;
		}
	}	
	if(cnt < n - 1) return INF;
	else return res;
}
int main(){
	cin >> n >>m;	
	for(int i = 0; i < m; i ++){
		int a, b, w;
		cin >> a >> b >>w;
		
		edges[i] = {a, b, w};
	}	
	int t = kruskal();	
	if(t == INF) puts("impossible");
	else cout << t <<endl;
}

染色法判别二分图

时间复杂度是 O(n+m), n 表示点数，m 表示边数

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010, M = 200010;
int n,m;
int h[N],e[M],ne[M],idx;
int color[N];      // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx++;
}
// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u,int c){
    color[u] = c;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!color[j]){
            if(!dfs(j,3-c)) return false;
        }
        else if(color[j] == c) return false;
    }
    return true;
}

int main(){
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    bool flag = true;
    for(int i=1;i<=n;i++)
        if(!color[i]){
            if(!dfs(i,1)){
                flag = false;
                break;
            }
        }
    if(flag) puts("Yes");
    else puts("No");
    return 0;
}

匈牙利算法

时间复杂度是 O(nm), n 表示点数，m 表示边数

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010, M=200010;
int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     
// 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool find(int x){
    for(int i=h[x];i!=-1;i=ne[i]){
        int j = e[i];
        if(!st[j]){
            st[j] = true;
            if(match[j]==0||find(match[j])){
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    cin >> n1 >> n2 >> m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        cin >> a >> b;
        add(a,b);
    }
    // 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
    int res = 0;
    for(int i=1;i<=n1;i++){
        memset(st,false,sizeof st);
        if(find(i)) res++;
    }
    cout << res;
    return 0;
}

常用数论

试除法判定质数

bool is_prime(int x){
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

试除法分解质因数

void divide(int x){
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0){
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

筛法求素数

//朴素筛法求素数
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}
//线性筛法求素数
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ ){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

试除法求所有约数

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

欧几里得算法

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

快速幂

求 m^k mod p，时间复杂度 O(logk)。
int qmi(int m, int k, int p){
    int res = 1 % p, t = m;
    while (k){
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

typedef long long ll;
ll qmi(int a,int b,int p){
    ll res = 1 % p;
    while(b){
        if(b & 1) res = res * a%p;
        a = a * (ll)a % p;
        b >>= 1;
    }
    return res;
}