模板集合

· · 个人记录

hello~ 这里是nihachu（叫niki就好）！

这里是各种算法的模板集合，主要是方便自己背板子用的，后续会不定期更新，希望能帮到和我一样的小伙伴，也希望各路大神可以帮忙指正或补充，thanks~

(部分代码来自网络，若有侵权，请联系我删除，感谢！)

一、二叉树相关：

1、深度优先：

前序遍历(根，左子树，右子树)

void dfs(int x){
    printf("%d\n",x);
    if(ls[x]) dfs(ls[x]);
    if(rs[x]) dfs(rs[x]);
}

中序遍历（左子树，根，右子树）

void dfs(int x){
    if(ls[x]) dfs(ls[x]);
    printf("%d\n",x);
    if(rs[x]) dfs(rs[x]);
}

后续遍历（左子树，右子树，根）

void dfs(int x){
    if(ls[x]) dfs(ls[x]);
    if(rs[x]) dfs(rs[x]);
    printf("%d\n",x);
}

2、广度优先：

层次遍历（从上到下，从左到右依次输出同一层的节点）：

void bfs(int x){
    q[++top] = x;
    for(int i = 1; i <= top; i ++){
        int now = q[i];
        printf("%d\n",now);
        if(ls[now]) q[++top] = ls[now];
        if(rs[now]) q[++top] = rs[now];
    }
}

二、动态规划相关：

1、01背包（已降维）

for(int i = 1; i <= n; i ++){
    for(int j = m; i >= w[i]; j --){
        dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
    }
}

2、完全背包

for(int i = 1; i <= n; i ++){
    for(int j = w[i]; i <= m; j ++){
        dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
    }
}

3、背包计数

for(int i = 1; i <= n; i ++){
    for(int j = m; i >= w[i]; j --){
        dp[j] += dp[j - w[i]];
    }
}

（若要求恰好为m，则dp[0]初始化为1，其他均为0）；

4、二进制拆分（用于多重背包）

for(int i = 1; i <= n1; i ++){
    scanf("%d %d %d",&a, &b, &c);
    for(int k = 1; k <= c; k <<= 1){
        v[++u] = k * a; w[u] = k * b;
        c -= k;
    }
    if(c) v[++u] = a * c,w[u] = b * c;
}

三、卡时间相关

1、快读

 int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}

2、快写

void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}

3、手动o2优化

#pragma GCC optimize(2)

四、并查集

1、查询 + 路径压缩

int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

2、合并x，y所属集合

void marge(int x, int y){
    int u = find(x), v = find(y);
    if(u == v) return;
    fa[u] = v;
}

3、合并x， y 所属集合（按秩合并）

void marge(int x, int y){
    int u = find(x), v = find(y);
    if(u == v) return;
    if(rk[u] > rk[v]) swap(u,v); // 把深度小的合并到深度大的上面； 
    fa[u] = v;
    rk[v] += rk[u] == rk[v]; //如果同级，则合并后深度加一，否则不变； 
}

五、单调队列

//n为数据个数，m为窗口长度； 
for(int i = 1; i <= n; i ++){
    if(q[head] <= i - m) head ++;
    while(head <= tail && a[q[tail]] < a[i]) tail --;
    q[++tail] = i;
    ans[i] = a[q[head]];
}
for(int i = m ; i <= n ; i ++){
    //对每个窗口中已选出的数据进行处理 ； 
}

六、图论

1、链式前向星

void add(int x, int y){
    to[++cnt] = y;
    nxt[cnt] = head[x];
    head[x] = cnt;
}

2、输出所有从x出发的边的终点和边权

for(int i = head[x];i;i = nxt[i]) 
    printf("%d %d",to[i],v[i]);

3、图的遍历

dfs：

void dfs(int x){
   vis[x] = 1; 
   printf("%d\n",x);
   for(int i = head[x];i;i = nxt[i])
    if(!vis[to[i]]) dfs(to[i]);
}

bfs :

void bfs(int x){
    z[++top] = x;
   for(int i = 1; i <= top; i ++){
     int now = z[top ++];
     printf("%d\n",now);
     for(int j = head[now]; j; j = nxt[j]){
        if(!vis[to[j]])
        vis[to[j]] = 1, z[++top] = to[j];
     }
}

4、欧拉路径/回路

1)判断是不是欧拉路径/回路

for(int i = 64; i <= 125; i ++){
        if(du[i] % 2)  jud ++ ; //记录入度为奇数的点
    }
   if(!jud) //是欧拉回路
   if(jud == 2) //是欧拉路径
   if(jud && jud != 2)//啥也不是

2)欧拉路径/回路的遍历

void dfs(int x){
    for(int i = head[x]; i; i = nxt[i])
    if(!vis[i]) vis[i] = 1, dfs(to[i]);
   printf("%d",x);
   }

3）遍历环并记录长度

void dfs(int x,int dt){
    if(vis[x]){
        ans = min(ans,dt - d[x]);
    }
    else{
        vis[x] = true;
        d[x] = dt;
        dfs(to[x],dt + 1);
    }
}

4）拓扑排序


for(int i = 1; i <= n ; i ++) if(du[i] == 0) z[++top];
for(int i = 1; i <= top; i ++){
    for(int j = head[z[i]]; j; j = nxt[j]){
        du[to[j]] --;
            if(du[to[j]] == 0) z[++top] = to[j];
            }
        }