图论

基础概念

• 度（Degree）：一个顶点上的度是指与该顶点相关联的边的条数，顶点$v$的度记作$d(v)$。
• 入度（In-degree）和出度（Out-degree）：对于有向图来说，一个顶点的度可细分为入度和出度。顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。
• 自环（Loop）：若一条边的两个顶点为同一个顶点，则此边称之为自环。
• 路径（Path）：在图上随便走，走出来的就是路径。
• 环：起点=终点的路径。
• 简单路径：每个点至多走一次的路径（点不能重复，边可以）。
• 简单环：去掉起点终点后变成简单路径（起点终点可以走两遍）。
• 完全图：所有点之间都有边。该图有$n$个顶点，$\dfrac{n\times(n-1)}{2}$条边。

无向图总度数一定是偶数，因为从什么都没有开始每次加一条边，就有两个点的度数加一。

特殊的图

• 树：无环，无向，连通$n$个点的树$n-1$条边。
  无环，无向，不连通？——森林（每个连通块都是一个树）。
  无环，连通，有向？——有向图的树。

  • 外向树：边都指向叶子节点的树
  • 
  • 内向树：边都指向根的树
  • 
    有环，无向，连通？——章鱼图/基环树。

  章鱼（$n$条边）变树：断掉环上的一条边。

  树变章鱼：任意连接一组边。

  扩展——树形DP。

  没有上司的舞会plus ：

  • 
    不可断环为树（数据范围）。

  1.对环上的每一个点做一次 树形DP
  2.环形DP

  • 
    代表选到环上第几个点/第i个点选没选/第1个点选没选。
  • 

如何找环呢？

从根节点开始 DFS，

直到从某一个点走到了它的祖先，

如果 DFS 途中找到了这个点的祖先，

那么就反向跳不断地跳到他的父亲，

直到找到这个点，

那么经历的所有点便组成了一个环。

• 仙人掌图

  • 边仙人掌图：把每一个点都换成一个环，边是用来连接不同的环的。
  • 点仙人掌图：用点连接的仙人掌图。
  • 一般也是 DP 题。
  • 做法：树形DP 环形DP交替进行：树形——环形——树形。
  • 

• 有向无环图（DAG）：

  • DP：状态看作点，转移看作边，其实 DP 就是 DAG。

• 二分图（无向图）：（染色问题：一个点和它相邻的点的颜色一定不同的图）图分为左边和右边两个部分，所有边都在中间，左边右边内部都没有边。

• 方格图：

  • 
  • 类似国际象棋的棋盘。

二分图判定

树是二分图。

只需要把深度为奇数的点放在左边，

深度为偶数的点放在右边（没有上司的舞会），

那么边一定全在中间。

什么图不是二分图呢？

有奇环的图就一定不是，没有奇环就是（环上的点数是奇数），

代码思路：随便找到一个点把它染成白色，再染相邻的点。

何时结束？

染完以后发现相邻有与自己颜色相同的点，那么就不是二分图。

二分图不一定连通。

图的存储

邻接矩阵

$f[i] [j]$代表从$i$到$j$有边。

• 好处：询问快，好写。
• 坏处：空间较大，没有办法处理重边。

边表（链式前向星）

• 建立$n$个链表
• 见深度理解链式前向星_ACdreamers的博客-CSDN博客_链式前向星
• 
• 

既然会存图了，那么我们做一下章鱼图DP吧！

对环上的每一个点做一个 树形DP

保证不要 DFS 到环上

做完 树形DP 后再对环做一个 环形DP 那么就做完了

最短路

• 单源最短路（一个点到其他所有点）
  • 三角不等式$(dist i,k <= dist i,j+dist j,k)$
  • 
• 多源最短路（多个点到所有点的最短路——多次单源最短路）

Floyed——多源最短路(DP)

条件：边权大于等于0 。

$F i,j,k$代表从$j$走到$k$中间经过的每个点编号都小于$i$。

现在又加了一条边。

这条边可选可不选。

但是$i$可以通过枚举解决。

进行一个状态压缩。

注意要先枚举中间点。

Bellman-Ford

首先，$i$到$j$之间最短路一定不超过$n-1$条边，

每次循环枚举所有的边来进行松弛操作，后面的边会被前面的边更新。

即使最差的顺序，倒着遍历，导致每次只能更新一条边，那最多也不会超过 $n-1$ 次操作。

所以就得到了如下代码，

是不是肥肠简单捏。

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 10000007
int n,dist[maxn],m,first[maxn];
int s[maxn],e[maxn],d[maxn];
int main()
{
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&s[i],&e[i],&d[i]);//起点，终点，长度
    }
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;//起点距离
    for(int i=1;i<n;i++)//最多n-1条边,最多松弛n-1次，因为如果倒着来的话，所有点的dist都未知，每次只能更新一个点，因此每轮会至少松弛一个点
        for(int j=1;j<=m;j++)//枚举边
        {
            dist[e[j]]=min(dist[e[j]],dist[s[j]]+d[j]);
        }
    return 0;
}

但是复杂度比 Dijkstra 高。

但是它能处理负边权和负环，因为它每一条边都会看$n-1$次，保证不会漏掉更优解。

如果进行 $n-1$ 次松弛后还能进行第 $n$ 次松弛，那么就有负环。

因为假如一张图所有的点的最短路都被求了出来，并且其中不存在负环，这时遍历每一条边进行松弛操作，我们会发现什么也不会发生。

若仅仅出现了负边权，其实也什么都不会发生。

举个例子：

对于这样一张图，进入环以后会发现：每条边被松弛一遍后，每个点的 $dist$ 值都是固定的，无法被更新。

而对于这样一张有负环的图，当遍历回原点这条边时，会发现它的$dist$变小了，那么在下一次的松弛操作中，就会有边受到这条边的影响而变小。

根据负环的定义：边权和为负数的环。我们可以知道，其实关键就是在于从进入环到回到起点的那一刻，起点的$dist$有没有被更新，而如果边权和为负数的话，那么该点一定会被更新，进而进入一种循环，环上的最短距离不断变小，不断绕圈圈，到最后变成负无穷。

导致了负环连出去的点最短路径都是负无穷。

SPFA

关于SPFA ，它死了。

和 BFS 不一样的地方就是一个点可能被扔进队列多次，

实际上就是 Bellman-Ford 的队列优化，

复杂度$O(nm)$近似$O(m)$

如果边权大于等于零，一定是用 Dijkstra$+$堆。

如果小于零那就是 SPFA 。

双端队列优化

在松弛操作的时候，假如这条边的终点没被标记，假如终点的dist值比队头要大，那就放在队尾，如果比队头小，那就加在队头。

代码：

for(int i=fir[now];i;i=ed[i].nxt)
        {
            int v=ed[i].to;
            if(dist[v]>dist[now]+ed[i].val)
            {
                dist[v]=dist[now]+ed[i].val;
                if(!righ[v])
                {
                    righ[v]=true;
                    if(!q.empty()&&dist[q.front()]<dist[v]) q.push_back(v);//队列不空防止RE，小的就放在队头，大的就放在队尾
                    else q.push_front(v);
                }
            }
        }

Dijkstra

图上边权大于等于0 。

复杂度 $O(n^2+m)$。

记$dist_i$代表从起点到$i$的最短距离。

$1$号点到自己距离为$0$。

其他点为无穷大。

把一号点放到右边，

进行一个松弛操作，

“用已知更新未知”。

用已知最短路的点更新未知最短路的点。

用dist最短的点去更新其他点，

更新过最短距离的点不会被再次更新

因为边权大于等于$0$，

假如$j$走到$i$，

并且$dist[i]$ < $dist[j]$，

$j$不可能走出比$dist[i]$ 还短的路，

因此$dist[i]$ 不会被更新。

Dijkstra+Heap优化

1.询问最小值。

2.删除最小值。

3.修改某些值。

大根堆：仿函数 greater<int>

用 pair 的话默认是按照 first 排序，其次按照 second 排序。

可以使用堆/线段树。

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000007
int dist[maxn],first[maxn];
int n,m,s;
bool righ[maxn];//这个点有没有放到右边去
struct point{
    int p,d;//原点到p的最短距离为d
    point(){}
    point(int a,int b){p=a;d=b;}
};
bool operator<(const point &a,const point &b)//STL默认大根堆，上面是大的
{
    return a.d>b.d;//小根堆
}
priority_queue<point> heap;
//松弛操作
struct edge
{
    int e,next;
    int d;//长度
}ed[maxn];
int cnt;
void add_edge(int u,int v,int w)
{
    cnt++;
    ed[cnt].next=first[u];
    ed[cnt].e=v;
    ed[cnt].d=w;
    first[u]=cnt;
}
void dijkstra(int s)
{
    memset(dist,0x3f,sizeof(dist));//全部都赋值为最大值
    dist[s]=0;//s到s
    for(int i=1;i<=n;i++)
        heap.push(point(i,dist[i]));//可以无变量名
    for(int i=1;i<=n;i++)
    {
        while(righ[heap.top().p])//有些点被拿到了右边但是左边没有删除
            heap.pop();
        point now=heap.top();
        heap.pop();
        int p=now.p;
        // int d=now.d;//未加堆优化版，找到目前dist最小的点
        // int p=-1;//代表还没选任何点
        // for(int j=1;j<=n;j++)//循环后就找到了在左边最短路最小的点
        // {
        //     if(!righ[j]&&(p==-1||dist[p]>dist[j]))//righ[]代表有没有放到右边去
        //         p=j;
        righ[p]=1;//放到右边，枚举出边
        for(int j=first[p];j; j=ed[j].next)//ed[j].e即为p的下一个点
        {
            int e=ed[j].e;
            int d=dist[p]+ed[j].d;
            if(dist[e]>d)
            {
                dist[e]=d;
                heap.push(point(e,d));//改不了那就丢一个新元素进去
            }
            // dist[ed[j].e]= min(dist[ed[j].e],dist[p]+ed[j].d);//或者这样
        }
    }
}
signed main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)
    {
        if(dist[i]==1061109567)
        {
            cout<<2147483647<<" ";
            continue;
        }
        printf("%d ",dist[i]);
    }
        
    return 0;
}

由于 Dijkstra 采用的是贪心策略，每个点只被加入堆中一次，这样的话一旦出现负环，那么明明可以绕很多圈让路径长度变为负无穷，但是 Dijkstra 只会跑一遍，导致贪心最优得出答案错误。

负边权也是同理，假如当前最小的$dist$值的点并没有连接负边权的点，那么 Dijkstra 就不会考虑不在考虑范围之内的负边，但往往这种时候选更大的$dist$点来获取该负边会更优。

例如该图，求 A 到 B 的最短路。

最小距离为2，但是 Djkstra 会认为是4。

堆的做法（优先队列）：

$(n+m) \times log(n+m)$

手写堆：$$(n+m)\times log_n$$(斐波那契堆会更快)

Johnson

一种多源最短路算法

新建一个虚拟节点零号点，把它向其它所有点连接一条边权为 0 的边，

然后用 Bellman-Ford 求出 0 号点到其它所有点的最短路，记为 $h_i$。

设存在一条从 $u$ 到 $v$ 权值为 $w$ 的边，把它的权值设置为 $w+h_u-h_v$，这样以每个点为起点，跑 $n$ 遍 Dijkstra 就可以求出任意两点间的最短路了。

如果不这样处理，将会导致负边权。

在新图上跑 Dijkstra 后，对于 $u\to{v}$ 的路径，结果是原来的最短路 $+\,h_s-h_t$，所以最后还要再 $-h_s+h_t$ 才能得到正确最短路。

原图：

新图：

一开始的预处理，到超级源点的最短距离要么就是零，要么就是负数，所以不需要初始数组为极大值。

但是如果是SPFA的话，需要判断是否有更新过，不然不会入队，所以还是要标记初始为极大值。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;
const int M = 6e3 + 10;

int n, m, edcnt;
int h[N];
int s[N],t[N],d[N];
int fir[N];
int dist[N];
bool vis[N];

struct edge
{
    int to, val, nxt;
}e[(M << 1) + N];
struct point
{
    int id,len;
    point(){}
    point(int a,int b):id(a),len(b){}
    bool operator < (const point &x)const
    {
        return len > x.len;
    }
};

void Add(int u, int v, int w)
{
    e[++edcnt].nxt = fir[u];
    e[edcnt].to = v;
    e[edcnt].val = w;
    fir[u] = edcnt;
}
void Dijkstra(int s)
{
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    dist[s] = 0;
    priority_queue<point> q;
    while(!q.empty()) q.pop();
    q.push(point(s,0));
    while(!q.empty())
    {
        point now = q.top();
        q.pop();
        if(vis[now.id]) continue;
        vis[now.id] = true;
        for(int i = fir[now.id]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            int d = dist[now.id] + e[i].val;
            if(d < dist[v])
            {
                dist[v] = d;
                if(!vis[v]) q.push(point(v,dist[v]));
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; ++i)
        scanf("%d%d%d",&s[i],&t[i],&d[i]);
    int tot = m;
    for(int i = 1; i <= n; ++i)
    {
        s[++tot] = 0;
        t[tot] = i;
        d[tot] = 0;
    }
    for(int i = 1; i <= n; ++i) // 多加了一个源点，所以最多松弛 n 次
        for(int j = 1; j <= n + m; ++j) // n+m条边
            h[t[j]] = min(h[t[j]], h[s[j]] + d[j]);
    for(int j = 1; j <= n + m; ++j)
        if(h[t[j]] > h[s[j]] + d[j])
        {
            printf("-1");
            return 0;
        }
    for(int i = 1; i <= m; ++i)
        Add(s[i], t[i], d[i] + h[s[i]] - h[t[i]]);
    for(int i = 1; i <= n; ++i)
    {
        Dijkstra(i);
        ll ans = 0;
        for(int j = 1; j <= n; ++j)
            ans += j * (dist[j] == 0x3f3f3f3f ? 1e9 : dist[j] - h[i] + h[j]);
        printf("%lld\n", ans);
    }
    return 0;
}

---

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;
const int M = 6e3 + 10;

int n, m, edcnt;
int h[N];
int fir[N];
int dist[N];
bool vis[N];

struct edge
{
    int to, val, nxt, from;
}e[(M << 1) + N];
struct point
{
    int id,len;
    point(){}
    point(int a,int b):id(a),len(b){}
    bool operator < (const point &x)const
    {
        return len > x.len;
    }
};

void Add(int u, int v, int w)
{
    e[++edcnt].nxt = fir[u];
    e[edcnt].from = u;
    e[edcnt].to = v;
    e[edcnt].val = w;
    fir[u] = edcnt;
}
bool SPFA(int s)
{
    bool inque[N];
    int times[N];
    memset(times, 0, sizeof(times));
    memset(inque, 0, sizeof(inque));
    memset(h, 0x3f, sizeof(h));
    queue<int> q;
    times[s] = 1;
    h[s] = 0;
    q.push(s);
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        inque[now] = false;
        for(int i = fir[now]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            int d = h[now] + e[i].val;
            if(d < h[v])
            {
                h[v] = d;
                if(!inque[v])
                {
                    inque[v] = true;
                    q.push(v);
                    times[v]++;
                    if(times[v] > n)
                        return false;
                }
            }
        }
    }
    return true;
}
void Dijkstra(int s)
{
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    dist[s] = 0;
    priority_queue<point> q;
    while(!q.empty()) q.pop();
    q.push(point(s,0));
    while(!q.empty())
    {
        point now = q.top();
        q.pop();
        if(vis[now.id]) continue;
        vis[now.id] = true;
        for(int i = fir[now.id]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            int d = dist[now.id] + e[i].val;
            if(d < dist[v])
            {
                dist[v] = d;
                if(!vis[v]) q.push(point(v,dist[v]));
            }
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        Add(u, v, w);
    }   
    for(int i = 1; i <= n; ++i)
        Add(0, i, 0);
    if(!SPFA(0))
    {
        printf("-1");
        return 0;
    }
    for(int i = 1; i <= m; ++i)
        e[i].val += h[e[i].from] - h[e[i].to];
    for(int i = 1; i <= n; ++i)
    {
        Dijkstra(i);
        ll ans = 0;
        for(int j = 1; j <= n; ++j)
            ans += j * (dist[j] == 0x3f3f3f3f ? 1e9 : dist[j] - h[i] + h[j]);
        printf("%lld\n", ans);
    }
    return 0;
}

负环判定

整个环权值的和为负

1. 做 SPFA 时候可以多记一个$cnt_i$
   代表到这个点的最短路经历了几条边
   如果这个数量超过了$n-1$，说明有负环
2. 如果一个点入队超过$n-1$次，也说明有负环
   在SPFA中入队一次说明在Bellman-Ford中被更新一次，入队次数$\le$更新次数。

差分约束

对应最短路中的 $d <= dist [i]+w[i]$

最大值对应最短路

解释：

对于每一个 $a_i$ ，都有一个$a_i$-$a_j$$\leqslant$$k_i$

也就是$a_i$$\leqslant$$a_j$+$k_i$

这不就是最短路中的松弛操作嘛！

要使这些条件都满足

式子上下相加

那么一定是对每一个不等式的右面之和取一个$min$

也就是求一个最小值最短路

---

那么同理

最小值对应最长路

树上差分

例子：对于树上的一些路径进行访问，问一条路径上的点被访问的次数。

每次有一个 $s,t$ 的询问，可以找到它们的公共祖先 lca，然后进行如下操作：

d[s]++;
d[t]++;
d[lca]--;
d[fa[lca]]--;

这样访问值的时候，访问以该节点为根的子树和即可。

而假如对边差分，可以把边权对应到较深的点上，然后就可以得到一下操作：

d[s]++;
d[t]++;
d[lca] -= 2;

---

P3128

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;

int n, k, ans;
int cf[N];
int dep[N];
int fir[N];
int st[N][25];
struct Edge
{
    int nxt, to;
}e[N << 1];
int cnt;

void add(int u, int v)
{
    e[++cnt].to = v;
    e[cnt].nxt = fir[u];
    fir[u] = cnt;
}
void dfs1(int u, int fa)
{
    for(int i = fir[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa) continue;
        st[v][0] = u;
        dep[v] = dep[u] + 1;
        for(int j = 1; j <= 23; j++)
            st[v][j] = st[st[v][j - 1]][j - 1];
        dfs1(v, u);
    }
}
int lca(int u, int v)
{
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 23; i >= 0; i--)
        if(dep[st[u][i]] >= dep[v])
            u = st[u][i];
    if(u == v) return u;
    for(int i = 23; i >= 0; i--)
        if(st[u][i] != st[v][i])
            u = st[u][i], v = st[v][i];
    return st[u][0];
}
int dfs2(int u)
{
    int sum = cf[u];
    for(int i = fir[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == st[u][0]) continue;
        sum += dfs2(v);
        ans = max(ans, sum);
    }
    return sum;
}
void update(int x, int y)
{
    cf[x]++;
    cf[y]++;
    int l = lca(x, y);
    cf[l]--;
    cf[st[l][0]]--;
}
int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; i++) 
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dep[1] = 1;
    dfs1(1, -1);
    for(int i = 1; i <= k; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        update(x, y);
    }
    dfs2(1);
    printf("%d\n", ans);
    return 0;
}

树上序列

树的存储方式： 当作无向图

概念略

自己也是自己的祖先

最近公共祖先问题（LCA）

公共祖先：两个点祖先的交集

最近：最靠下的公共祖先

最近公共祖先有什么用呢？

判断两个点怎么走

那么怎么求呢？

暴力？

若假定 $p1 p2$ 深度相同

可以让左右两点同时向上跳

某时刻两点重合

意味着遇到了公共祖先

1. 调整深度
2. 一起跳

优化：

慢是因为一步一步跳的

所以我们可以考虑每次可以每次多跳几步

倍增求LCA

$f [i] [j]$ 表示从 $i$ 向上跳 $2^j$ 步会跳到哪个点

需要预处理

$f[i] [0]=fa[i]$

$2^j$=$2^{j-1}$ + $2^{j-1}$

$f[i] [j]=f[ [i] [j-1] ] [j-1]$

向上跳 $2^{j-1}$ 步再跳一遍

那么求出来可以有什么用呢？

求 $p1$ 和 $p2$ 之间的边权最小值

最小值？

不支持修改操作。

DFS 序求 LCA

对于 $u$ 和 $v$ 的 $lca$，在 dfs 序上 $lca$ 一定在 $u$ 和 $v$ 之间，于是我们可以维护 dfs 序区间最小的点的父节点即 $lca$。

注意区间长度本来为 $dfsn_{y}-dfsn_x+1$，但是由于查询的是 $[dfsn_x+1,dfsn_y]$，所以区间长度为 $dfsn_y-dfsn_x$。

#include <iostream>
#include <vector>
using namespace std;
const int N = 5e5 + 8;

int idx, n, m, root, cnt;
int dfsn[N], st[25][N], fir[N];
int Log2[N];
struct Edge
{
    int to, nxt;
}e[N << 1];

void init()
{
    Log2[0] = -1;
    for (int i = 1; i <= n; i++)
        Log2[i] = Log2[i / 2] + 1;
}
int get(int x, int y)
{
    return dfsn[x] < dfsn[y] ? x : y;
}
void add(int u, int v)
{
    e[++cnt].to = v;
    e[cnt].nxt = fir[u];
    fir[u] = cnt;
}
void dfs(int u, int fa)
{
    dfsn[u] = ++idx;
    st[0][idx] = fa; // 以 idx 为起点长度为 (1 << i) 的区间内 dfsn 最小的点的父亲
    for (int i = fir[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == fa) continue;
        dfs(v, u);
    }
}
int lca(int x, int y)
{
    if (x == y) return x;
    if (dfsn[x] > dfsn[y]) swap(x, y);
    int d = Log2[dfsn[y] - dfsn[x]]; // +1 -1
    return get(st[d][dfsn[x] + 1], st[d][dfsn[y] - (1 << d) + 1]); // [dfsn_u + 1, dfsn_v]
}
int main()
{
    scanf("%d%d%d", &n, &m, &root);
    for (int i = 2, u, v; i <= n; i++)
    {
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    init();
    dfs(root, 0);
    for (int i = 1; i <= Log2[n]; i++) // Log2[i] 下取整
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            st[i][j] = get(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    for (int i = 1, u, v; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}

树的序列化(并不是完整的线段树)

• 树状数组
• 线段树

1.DFS序

• 作用：树上子树查询修改
  • 1. 以$P$为根子树权值和
  • 2. 把以$P$为根的子树全部加上某一个值
  • 3. 把根换成$P$

任何一段子树都对应一段序列上的区间

1. 递归求出
2. BFS 求出

代码见 $VScode$

序列是写好了，那么怎样实现它的作用呢？

$1.$ $2.$都好说

但是3.怎么实现呢

会改变 dfs 序

解决方法：

只换一次

哪些点的子树会发生变化？

只有$1$号点到$p$号点路径上的点的子树才会发生变化

不会影响其它点

把一段区间的询问改成两段区间的询问就可以了

---

2.括号序列

它能解决什么样的问题呢？

链上操作

用 LCA 把这段链分成两部分

这样就可以分别进行求解（ 可能LCA被算了两次，减去一个就可以了 ）

$5 \to 1$

$1 \to 9$

链求和转换为两端区间求和

只能用来求链的和

不能求最大值最小值

可以用倍增来做

生成树

• 概念：$n$个点中找$n-1$条边，使它组成一颗树

1.Prim

每次选择与生成树这个连通块的最小的一条连接的边，加到这个连通块内。

维护两个集合：

左边的集合：还没有加到生成树中的点

右边的集合：加到生成树的点

$dist$ 数组：点i经过一条边到生成树上的最短距离

走不到就是无穷大（初始化）

一开始生成树上是没有点的

所以点 $1$ 的 $dist$ 就是 $0$

然后用一号点更新其他点

每轮选左边 $dist$ 值最小的点加到右边然后用它来更新其它点

把所有点都放到右边以后就做完了

这就是PRIM算法（Djkstra的孪生兄弟）

它与 Dijkstra 最大的不同就是 Dijkstra 维护的是到起点的距离，而 Prim 维护的是到已经生成的最小生成树的连通块的距离。

堆优化：

void prim(int s)
{
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    heap.push(point(s, dist[s]));
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        if (vis[t.p]) continue;
        vis[t.p] = true;
        for (int i = fir[t.p]; i; i = ed[i].next)
        {
            int v = ed[i].e;
            if (ed[i].d < dist[v])
            {
                dist[v] = ed[i].d;
                heap.push(point(v, dist[v]));
            }
        }
    }
}

$n^2$ 代码：

int prim()
{
    vis[1] = 1;
    int res = 0;
    for(int i = 1; i <= n; i ++) dist[i] = graph[1][i];
    for(int j = 1; j <= n; j ++)
    {
            int minc = INF, p;
            for(int i = 1; i <= n; i++){
                if(vis[i] == 0 && dist[i] < minc)
                {
                    minc = dist[i];
                    p = i;
                }
            }
            if(minc == INF) return -1;
            vis[p] = 1;
            res += dist[p];
            for(int i = 1; i <= n; i ++)
            {
                if(vis[i] == 0 && dist[i] > graph[p][i])
                    dist[i] = graph[p][i];
            }
    }
    return res;
}

复杂度：$O((N+M)logN)$ 适合稠密图，也就是点少于边。

2.Kruskal

前置：并查集

支持两种操作：

• 查询两元素是否在同一集合中
• 合并两集合

代码也是十分的好写啊

假如是条链呢？

那这样就太慢了

我们可以进行一些优化

启发式合并

之前不是谁都可以做父亲吗

现在谁的子树大，谁就是父亲

按秩合并

谁的深度大，谁就是父亲

路径压缩

不改变合并过程

但在get_root找根的时候

把所有点的父亲都变成根

因为我们不关心树上的父子关系，我们只关心根是谁

贪心+并查集

实现

将边从小到大排序，从小到大每次挑一个加入到最小生成树中，若形成环则跳过，判断环可以用并查集实现。

当在边数远大于点数的稠密图中，Kruskal 会重复判断一些边导致超时，这时 Prim 更优。

所以 Kruskal 适合边数较少的稀疏图。

基础

AcWing1140

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int n;
int w[N][N];
int dist[N];
bool st[N];

int prim()
{
    int res = 0;
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for(int i = 1; i <= n; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        res += dist[t];
        st[t] = true;
        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], w[t][j]);
        
    }
    return res;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> w[i][j];
    cout << prim() << endl;
    return 0;
}

AcWing1141

#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 210;

// 求原图的最小生成“森林”
// 总边权减去生成的边权即可

int n, m;
int p[N];
struct edge
{
    int a, b, w;
    bool operator < (const edge &t) const
    {
        return w < t.w;
    }
}e[M];

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


int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[i] = {a, b, c};
    }
    sort(e + 1, e + 1 + m);
    int res = 0;
    for(int i = 1; i <= m; i++)
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
        if(a != b) p[a] = b;
        else res += w; // 在找最小生成树的时候把不需要的边给存起来就好了
    }
    cout << res << endl;
    return 0;
}

AcWing1142

#include <bits/stdc++.h>
using namespace std;
const int N = 310, M = 11111;

int n, m;
int p[N];
struct edge
{
    int a, b, w;
    bool operator < (const edge &t) const
    {
        return w < t.w;
    }
}e[M];

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

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 0; i < m; i++)
        cin >> e[i].a >> e[i].b >> e[i].w;
    sort(e, e + m);
    int res = 0;
    for(int i = 0; i < m; i++)
    {
        int a = find(e[i].a), b = find(e[i].b);
        int w = e[i].w;
        if(a != b)
        {
            p[a] = b;
            res = w;
        }
    }
    cout << n - 1 << ' ' << res << endl;
    return 0;
}

AcWing1143

#include <bits/stdc++.h>
using namespace std;
const int N = 2200, M = 10010;

int p[N];
int n, m;
struct edge
{
    int a, b, w;
    bool operator < (const edge &t) const
    {
        return w < t.w;
    }
}e[M];

// 相当于缩点，变完以后求一个最小生成树
// 其实直接跑最小生成树即可
int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    int cnt = 0;
    int res = 0;
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 0; i < m; i++)
    {
        int g, u, v, w;
        cin >> g >> u >> v >> w;
        if(g == 1)
        {
            int a = find(u), b = find(v);
            p[a] = b;
            res += w;
        }
        else e[++cnt] = {u, v, w};
    }
    sort(e + 1, e + 1 + cnt);
    for(int i = 1; i <= cnt; i++)
    {
        int a = find(e[i].a), b = find(e[i].b);
        if(a != b)
        {
            p[a] = b;
            res += e[i].w;
        }
    }
    cout << res << endl;
    return 0;
}

AcWing1144

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 2e6 + 7; // 严格来说最多有 2mn - m - n 条边
// 由于边权只有两种，所以直接按照顺序建边即可，无需排序

int n, m;
int ids[N][N];
int p[N * N];
int cnt;

struct edge
{
    int a, b, w;
}e[M];

// 注意：如果边权可正可负，所以不一定是最小生成树的问题
// 而这个问题边肯定越少越好
int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
void get_edges()
{
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    int dw[] = {1, 2, 1, 2};
    for(int z = 0; z < 2; z++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                for(int u = 0; u < 4; u++)
                    if((u & 1) == z)
                    {
                        int x = i + dx[u], y = j + dy[u];
                        int w = dw[u];
                        if(x < 0 || x > n || y < 0 || y > m) continue;
                        int a = ids[i][j], b = ids[x][y];
                        if(a < b) e[++cnt] = {a, b, w};
                    }

}

int main()
{
    cin >> n >> m;
    int res = 0;
    int x1, y1, x2, y2;
    for(int i = 1, t = 1; i <= n; i++)
        for(int j = 1; j <= m; j++, t++)
            ids[i][j] = t;
    for(int i = 1; i <= n * m; i++)
        p[i] = i;
    while(cin >> x1 >> y1 >> x2 >> y2)
    {
        int a = ids[x1][y1], b = ids[x2][y2];
        p[find(a)] = find(b);
    }
    get_edges();
    for(int i = 1; i <= cnt; i++)
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
        if(a != b)
        {
            p[a] = b;
            res += w;
        }
    }
    cout << res << endl;
    return 0;
}

扩展

• 任意一颗最小生成树一定可以包含无向图中最小的边。
• 给定一张无向图，若从中选出小于 $n - 1$ 条边使其构成一个生成森林，然后再从剩下的边中选取 $m - k$ 条边使得它成为一颗生成树，并且选出的权值之和最小。那么该生成树一定可以包含这 $m - k$ 条边中连接生成森林的两个不连通节点的权值最小的边（相当于缩点后求最小生成树）。

AcWing1146

虚拟源点的思想。

让这 $n + 1$ 个点连通，求个最小生成树即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 310;

int n;
int w[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 0;
    int res = 0;
    for(int i = 0; i <= n; i++)
    {
        int t = -1;
        for(int j = 0; j <= n + 1; j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true;
        res += dist[t];
        for(int j = 0; j <= n; j++) dist[j] = min(dist[j], w[t][j]);
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &w[0][i]);
        w[i][0] = w[0][i];
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &w[i][j]);
    printf("%d\n", prim());
    return 0;
}

AcWing1145

可以先二分后遍历。

也可以用并查集维护连通块的数量。

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = N * N / 2;
typedef pair<int, int> PII;
#define x first 
#define y second

// 找一个最小的 d 值，使得将所有 > d 的边删完后连通块的个数 <= k
// 用并查集维护连通块数量即可，当它等于 k 时，此时的边权就是答案

int n, k, m;
PII q[M];
int p[N];
struct edge
{
    int a, b;
    double w;
    bool operator < (const edge &t) const
    {
        return w < t.w;
    }
}e[M];
double dist(int a, int b)
{
    int dx = q[a].x - q[b].x;
    int dy = q[a].y - q[b].y;
    return sqrt(dx * dx + dy * dy);
}
int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> q[i].x >> q[i].y;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j < i; j++)
            e[++m] = {i, j, dist(i, j)};
    sort(e + 1, e + m + 1);
    for(int i = 1; i <= n; i++) p[i] = i;
    int cnt = n;
    double res = 0;
    for(int i = 1; i <= m; i++)
    {
        if(cnt == k) break; // 防止了一开始 k = cnt 的情况
        int a = find(e[i].a), b = find(e[i].b);
        double w = e[i].w;
        if(a != b)
        {
            p[a] = b;
            cnt--;
            res = w; // 防止了 k = 0 的情况
        }
    }
    printf("%.2lf\n", res);
    return 0;
}

AcWing346

每次合并连通块的时候，要把这两个连通块变成一张完全图，这样合并到最后得到的也是完全图。

加边，最小只能加原来的边权加一，因为要保证最小生成树不变且唯一。

#include <bits/stdc++.h>
using namespace std;
const int N = 6010;
const int M = (N * N) >> 1;

int n;
int p[N], siz[N];
struct edge
{
    int a, b, w;
    bool operator < (const edge &t) const 
    {
        return w < t.w;
    }
}e[M];

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


int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 1; i < n; i++)
            scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].w);
        sort(e + 1, e + n);
        for(int i = 1; i <= n; i++) p[i] = i, siz[i] = 1;
        int res = 0;
        for(int i = 1; i < n; i++)
        {
            int a = find(e[i].a), b = find(e[i].b);
            int w = e[i].w;
            if(a != b)
            {
                res += (siz[a] * siz[b] - 1) * (w + 1);
                siz[b] += siz[a];
                p[a] = b;
            }
        }
        cout << res << endl;
    }
    return 0;
}

AcWing1148

严格次小生成树。

1. 先求最小生成树，然后依次枚举删去最小生成树中的边再跑最小生成树。

这样做是 $O(mlogm + nm)$

这样做得到的只是次小生成树，不保证严格次小。

2. 先求最小生成树，然后依次枚举非树边，然后将该边加入树中，同时从树中这个环上任意去掉一条边，使得最终的图是一颗树，那么一定能求出次小生成树。

要保证求得是仅次于最小的最小，所以删去的边要尽可能大，其实就是求树上任意两点间的一个极值，这个可以用倍增来做，也可以暴力预处理。

复杂度： $n^{2}+m$

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 10010;
typedef long long ll;

int n, m, cnt;
int p[N];
int dist[N][N];
int dist2[N][N];
struct edge
{
    int a, b, w;
    bool f = false;
    bool operator < (const edge &t) const
    {
        return w < t.w;
    }
}ed[M];
struct Edge
{
    int nxt, to, val;
}e[N << 1]; // 建树即可
int fir[N];

void add(int u, int v, int w)
{
    e[++cnt].to = v;
    e[cnt].nxt = fir[u];
    e[cnt].val = w;
    fir[u] = cnt;
}
int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
void dfs(int u, int fa, int maxd, int maxd2, int d[], int d2[])
{
    d[u] = maxd, d2[u] = maxd2;
    for(int i = fir[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa) continue;
        int td1 = maxd, td2 = maxd2; // 保证每次循环 td1 和 td2 初值一样
        if(e[i].val > td1)
        {
            td2 = td1;
            td1 = e[i].val;
        }
        else if(e[i].val < maxd && e[i].val > maxd2) td2 = e[i].val;
        dfs(v, u, td1, td2, d, d2);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        ed[i] = {a, b, w};
    }
    sort(ed + 1, ed + m + 1);
    for(int i = 1; i <= n; i++) p[i] = i;
    ll sum = 0;
    for(int i = 1; i <= m; i++)
    {
        int a = ed[i].a, b = ed[i].b;
        int pa = find(a), pb = find(b), w = ed[i].w;
        if(pa != pb)
        {
            p[pa] = pb;
            sum += w;
            add(a, b, w);
            add(b, a, w);
            ed[i].f = true; // 是树边
        }
    }
    ll res = 1e18;
    for(int i = 1; i <= n; i++) dfs(i, -1, -1e9, -1e9, dist[i], dist2[i]);
    // 当前点编号，父节点编号，当前边权最大值
    for(int i = 1; i <= m; i++)
        if(!ed[i].f)
        {
            int a = ed[i].a, b = ed[i].b, w = ed[i].w;
            if(w > dist[a][b])
                res = min(res, sum + w - dist[a][b]);
            else if(w > dist2[a][b]) res = min(res, sum + w - dist2[a][b]);
        }
    printf("%lld\n", res);
    return 0;
}

3.次小生成树

我们发现次小生成树肯定是通过最小生成树来求的（替换一条边）

路径上找到最大的 V1 进行替换

换为$V_2$

怎么找最大的边呢？

进行一个倍增 LCA

在 LCA 的过程中找到最大值

1.先求最小生成树

2.用非树上的边替换树上链的最大值

3.求最大值可以用 LCA 来做

我不倍增求了

我暴力！

$O(nm)$

因为 Kruscal 求的时候对每条边排了个序

所以可以用排的序对非树边从小到大去枚举

以这张图为例

先一点点求一个$V_1$，也就是加粗的边

然后$V_2$仅次大于$V_1$

我们发现在$V_2$的链上有两条加粗的边，也就是求$V_1$的时候访问过了

假如用$V_2$替换掉这两条加粗边中的一条，那么会不会是次小生成树

设加粗边中的一条长度为$a$

那么分别替换后树的变化

很明显，在$V_1$的时候就替换$a$比在$V_2$的时候再替换$a$还要小

而在$V_1$的时候并没有替换$a$

所以$V_2$替换了$a$一定不会是次小的

因为拿$V_1$替换$a$是更优的

换而言之

一条边之前已经被更小的边判断过了

拿更大的边去判断已经判断过的边是没有意义的

也就是把非树边从小到大枚举

整个树上的边最多只需要被判断一次就够了

所以复杂度就变为了$O(m+n)$

那怎么保证只判断一次呢？

遍历一次就把它删掉

当然是用并查集咯

假设这是第一次遍历

那么就把这条路径上的点并为一个集合

第二次遍历

因为右下角的那个点更深，因此向上跳

发现跳到了之前已经跳到过的点

那么就直接跳到它的祖先

也就是向上跳一步

就把它加到它父亲的并查集里

再跳到它父亲的祖先位置

换句话说

假如某条边已经被考虑过了

那么就把它连接的两个点加到同一个并查集中

这样就可以保证每个点只访问了一次

并查集$O(1)$查询

欧拉路

欧拉路径

一条路径经过所有的边且只经过一次。

若起点和终点相同，则称之为欧拉回路。

无向图存在欧拉回路的条件：所有点的度数都为偶数。

无向图存在欧拉路径： 恰有两个点度数为奇数（起点和终点）。

有向图存在欧拉回路：所有点都满足 入度等于出度。

有向图存在欧拉路径：恰有一个点入度比出度多一（终点），另一个点出度比入度多一，其余点入度和出度相同。

Hierholzer

从起点开始 DFS ，然后枚举它的出边，继续 DFS 。

走过的边都标记（删边），遇到走过的边就continue。

回溯的时候再压入栈内，因为如果一开始就压栈，

看这张图，$1\to{2}\to{3}$，

遍历到 $3$ 的时候，那么栈内现在就是 $1 2 3$。

然后再遍历 $3$ 的出边，万一选了 $3\to{1}$ 这条边，那么再把 1 加入栈中，发现没法走了，回溯，接着遍历剩下的边，这时我们发现答案是错的，因为 $3\to{1}$ 这条边出现的时机很尴尬，如果它现在就出现了，那么就没法遍历 $4$ 和 $5$ 了，而由于回溯操作，我们可以悔棋，来调整它出现的顺序使其合理。

所以我们可以回溯后再让它进栈，因为这样的话遍历到 $1$ 发现没法走的时候，$1$ 会被加入栈，而 $3$ 不会，因为它还有其它出边要遍历，这样就可以给 $1$ 这个终点预留一个“上一个点”的位置，直到从 $3\to{5}\to{4}\to{3}$ 的时候，$3$ 会被加入栈，这时 $3\to{1}$ 这条边出现的顺序就正确了，因为 $3$ 的所有出边都已经遍历完了，不会出现其它边要出现在它之前的情况，然后往前回溯也是同理。

再举个例子便于理解：

对于这样一张图，

如果先递归后压栈，那么得到的欧拉路径为：

${9}\to{6}\to{3}\to{2}\to{1}\to{4}\to{2}\to{5}\to{6}\to{7}\to{8}\to{5}\to{4}$

如果先压栈后递归，得到的欧拉路径为：

${9}\to{6}\to{3}\to{2}\to{1}\to{4}\to{2}\to{5}\to{4}\to{6}\to{7}\to{8}\to{5}$

这里后半段应该是 ${5}\to{6}\to{7}\to{8}\to{5}\to{4}$，但是如果在$5$处往下递归的时候递归到 $4$ 直接压栈，就会导致后面 ${5}\to{6}\to{7}\to{8}$ 这个环不能插在它前面。

对于有向图，最后压栈的是前几个被遍历的，因此答案是反的，想办法 reverse 一下就好了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,st,cnt;
int d[1000][1000],ans[1000],f[1000];
stack<int> S;
void dfs(int u)
{
    for(int v=1;v<=n;v++)
    {
        if(d[u][v])
        {
            d[u][v]--,d[v][u]--;//删边
            dfs(v);
        }
    }
    S.push(u);
}
int main()
{
    int p=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        d[a][b]++,d[b][a]++;
        f[a]++,f[b]++;
    }
    for(int i=1;i<=n;i++)
    {
        // cout<<f[i]<<endl;
        if(f[i]%2==1)
        {
            st=i;
            cnt++;
        }
    }
    if(cnt!=2)
    {
        cout<<"No"<<endl;
        return 0;
    }
    cout<<st<<endl;
    // S.push(st);
    dfs(st);
    while(!S.empty())
    {
        ans[++p]=S.top();
        S.pop();
    }
    reverse(ans+1,ans+p+1);
    for(int i=1;i<=p;i++)
        printf("%d ",ans[i]);
    return 0;
}
// 9 12
// 1 2
// 1 4
// 2 4
// 2 5
// 4 5
// 2 3
// 5 6
// 3 6
// 6 7
// 7 8
// 8 5
// 6 9

对于链式前向星，也可以这样写：

int edcnt = 1;
stack<int> ans;
void dfs(int x)
{
    for(int i = head[x];i;i = nex[i])
    {
        int y = to[i];
        if(vis[i]) continue;
        vis[i] = 1;
        vis[i ^ 1] = 1;
        dfs(y);
    }
    ans.push(x);
}

还可以这样写

void ola(int x)
{
    for(int i=fir[x];i;i=fir[x])
    {
        int v=e[i].to;
        fir[x]=e[i].nxt;
        ola(v);
    }
    S.push(x);
}

这样就相当于直接在原图上进行修改了。

练习题

BZOJ3724 Krolestwo：

题解

AcWing366

本题建立双向边的有向图，边数$\times{2}$，记得空间开两倍，然后易得每个点的入度都等于出度，那么就在这上面当成有向图的欧拉回路就可以了。

题解

DAG拓扑排序

有向无环图可以称作拓扑图

拓扑序列：所有的边都是从前指向后的。

并不是所有图都有拓扑序，有环就不行。

1. 统计每个点的入度
2. 将所有入度为 $0$ 的点入队
3. BFS（取出队头元素，遍历所有它的出边）

假设 $t\to{j}$，

$d_j$ 代表 $j$ 的入度。

入度为 $0$ 说明没有任何一点在我前面。

所有入度为 $0$ 的点都可以当作起点。

所以第一步就是把所有入度为 $0$ 的点入队。

然后取出队头，枚举出边。

然后删掉这条边（$t\to{j}$）

就是 $d[j]-1$.

假如入度为 $0$ 就让它入队

如果有环

那么一定有一些点不会入队

如果一个图上并没有环

那么就可以把它拓扑掉

一个有向无环图一定有入度为$0$的点

反证法：

假如每个点的入度都不为$0$

那么一定可以沿着某个点无穷无尽的往上找

假如一共$n$个点

当找到第$n+1$的点时这个图就出现了环

所以有向无环图至少存在一个入度为零的点

把它作为突破口

挖墙脚

加入队列的顺序就是拓扑序列

DFS树

生成过程：

生成结果：

首先我们定义生成的边为树边，指向祖先的边称作回边，

遍历时遇到子树节点的边叫做前向边，遍历时遇到访问过的非祖先节点形成的边叫做横叉边。

观察这棵树，我们不难发现一些结论：

1. 生成树中，回边连接的一定是子孙节点。如果连接的是兄弟节点，那么肯定会沿着这条“回边”继续 DFS 下去，那么这条回边将会成为树边，“兄弟”节点也不再是兄弟关系，而是子孙关系。
2. 当树边 $u\to{v}$ 不存在连接它祖先和它的子孙节点的回边时，它是桥。
3. 回边一定不是桥。
4. 假如无向连通图有桥，那么就不可能使每条边给定一个方向后成为一个强连通图。因为假定 $uv$ 桥的方向是 $u\to{v}$，那么此时就不存在 $v\to{u}$ 的一条路径。
5. 假如无向连通图无桥，那么就可以使每条边给定一个方向后成为一个强连通图，使树边均向下，回边均向上。
6. 根节点可以移动到任意节点，任意节点都可以回到根节点。
7. 回边和横叉边的终点时间戳一定大于起点。
8. 对于每个强连通分量中的 dfs 生成树，必然存在一个点是其它所有点的祖先，即根节点 $u$ 是 dfs 序最小的点，若存在一个点$v$不在以$u$为根的树中，那么一定存在一条 $u\to{v}$ 的回边或者横叉边，而这两种边出现则意味着 $v$ 一定在之前被访问过，而这与 $u$ dfs 序最小矛盾。

比如本图中$5\to{2}$为回边，$1\to{5}$ 为前向边，$3\to{4}$为树边。

而改变一下 dfs 的顺序那么 dfs 生成树的形态将会不同。

比如上面两图。

仅改变了遍历顺序，生成的 dfs 树的形态便不同，每条边的性质也可能不同。

连通性

基本概念

图解理解更佳

• 点的连通性：无向图中，若点 $i$ 到点 $j$ 有路径，那么 $i$ 和 $j$ 就是连通的。
• 连通图：无向图中，任意两点间均有路径。
• 连通分量：分量其实就是子图，特指无向图。无向图的连通分量是它的最大连通子图，也就是说对于一个点蔓延出去的所有边，不能再往上加边了，而不是边数最多的连通子图，因此一个无向图可以有多个连通分量，连通分量也叫做连通块。也叫做极大连通分量，是一个概念。任何连通图的连通分量有且只有一个，即它本身。极小连通分量是在保持连通性的前提下的最小子图，形态是一棵树。
• 强连通图：特指有向图。有向图中，点 $i$ 到点 $j$ 有路径，则称这两点强连通。若任意一对顶点之间是强连通的，那么就是强连通图。
• 强连通分量：有向图中的极大强连通子图。与上面类似的，极大强连通分量与极小连通分量。
• 生成树：连通图中包含所有顶点的极小连通子图。
• 桥：无向图中，若删除了一条边，整个图的连通分量发生了改变，那么这条边就是桥。桥其实就是连通各个连通块之间的唯一的边。
• 生成森林：即一个非连通图中，包含多个连通块，每个连通块的生成树所组成的集合。

Tarjan求强连通分量

有向图求 SCC

我们维护两个变量：

$dfn_i$ 代表第 $i$ 号点的遍历次序（时间戳），也就是第几个被搜索到的。

$low_i$ 代表第 $i$ 号点经过最多一条非树边可达的与它强连通的点的 dfs 序，

$low(p)$ 可以通过 DP 得到，

对于某个以 $p$ 为起点的边 $p\to{q}$

如果 $q$ 未访问过，则 $q$ 在 $p$ 的子树上，如果某节点 $r$ 从 $q$ 起可以经过最多一条回边可以到达，那么从 $p$ 开始也可以到达（先从 $p$ 到 $q$ 再从 $q$ 到 $r$），所以可以先递归处理 $q$，然后更新$low(p)=\min(low(p),low(q))$。

如果 $q$ 已经访问过，并且 $p$ 与 $q$ 强连通，那么 $low(p)=\min(low(p),dfsn(q))$，其实就是访问到了非树边。

强连通性不存在传递性。比如 $u$ $v$ 之间强连通，$v$ $q$ 之间强连通，那么 $u$ $q$ 之间不一定强连通，$u\rightarrow v \leftarrow q$，因此只能用 $q$ 的 $dfsn$ 来更新 $p$ 的 $low$。

那么我怎么确定一个点是否可达呢？

因为回边和横叉边都指向 dfs 序较小的节点，而前向边又不影响上述转移方程，所以我们只需要确定哪些点比该点的 dfs 序小切能到达该点，这可以用一个栈来维护。

每次搜到新点就让它入栈，对点 $p$ 的子树搜索结束时，若$low(p)=n<dfsn(p)$，设 dfs 序为 $n$ 的点为 $q$，则 $p$ 点可达的 $q$ 点都可达（$q$ 是 $p$ 的子树中经过不超过一条非树边能够到达的 dfs 序最小的点，这么说 $q$ 是 $p$ 的祖先），而 $q$ 可能不止 $p$ 这一颗子树，所以 $p$ 应当留在栈内，因为它们都可能通过 $p$ 强连通，都可能是一个强连通分量。

也就是说，栈内的元素是当前搜索到的可能为强连通分量的元素，一个树在没有把它的若干子树搜索完全的情况下，之前搜索的树的子树不会出栈，出栈即意味着找到了一个强连通分量，当且仅当返回时发现$low(p)=dfsn(p)$。

显然，这样维护的栈内元素的 $dfsn$ 是递增的。

每个点的 $low()$ 值初始化为它的 $dfsn$。

我们实际上在找的每个节点的 $low()$ 值就是它在它所在的强连通分量的根节点的 $dfsn$。

一个点的子树搜索完毕时，它的 $low()$ 才会被更新。

得到的强连通分量编号的顺序符合拓扑序（编号越小，拓扑序越靠后）。

把每个强连通分量缩为一个点之后，得到的是一张有向无环图，因为只要能遍历到其中一个点，就一定能遍历到该强连通分量的所有点。

强连通分量中，tarjan 关注的是在不在一个强连通分量内。

而割点割边问题中关注搜索子树的个数。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
stack<int> s;
vector<int> g[N];
vector<int> g_2[N];
//cscc代表强连通分量的数量，scc代表每个点所属的强连通分量的编号，ins代表是否在栈中
int dfsn[N],low[N],ins[N],scc[N],deep,cscc,n;
void tarjan(int p)
{
    low[p]=dfsn[p]=++deep;
    ins[p]=1;
    s.push(p);
    for(auto &q:g[p])//遍历出边
    {
        if(!dfsn[q])//未访问
        {
            tarjan(q);
            low[p]=min(low[p],low[q]);
        }//访问过且q可达p，因为栈中元素强连通
        else if(ins[q]) low[p]=min(low[p],dfsn[q]);//注意这里为什么是dfsn[q]而不是low[q]
    }
    if(low[p]==dfsn[p])
    {
        int top=0;
        cscc++;
        while(top!=p)
        {
            top=s.top();
            s.pop();
            ins[top]=0;
            scc[top]=cscc;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)//原图不一定是强连通图，因此每个节点都要看一遍
        if(!dfsn[i])//未访问过
            tarjan(i);
    for(int i=1;i<=n;i++)
        for(auto j:g[i])//以i为起点的出边
            if(scc[i]!=scc[j])//如果不是一个强连通分量，那就可以把两个强连通分量当作两个点连接起来
                g_2[scc[i]].push_back(scc[j]);//j是i的出边，即j的强连通分量是i的强连通分量的出边
    return 0;
}

重边与自环对于有向图求强连通分量来说没有影响。

Tarjan求割点与桥

无向图

首先我们来明确一下这两个概念的定义：

• 割点：删去这个点会使无向图的连通分量数增加。
• 桥（割边）：删去这条边会使无向图的连通分量数增加。

那么我总不能把每条边和每个点都删掉看看吧，这样肯定行不通。

如何求割点与割边？

割点

在无向图中，$low$ 值为不经过父亲节点能到达的 dfsn 最小的节点 ，换句话说，是经过以自身为根节点的子树中至多一条非树边能够到达的最小 dfs 序的点。

无向图中，只需要考虑回边，因为无向图的 dfs 树不存在横叉边和前向边。

设以 $p$ 为根的子树为 $subtree(p)$，那么 $low(p)$ 就是 $subtree(p)$ 中的点和通过一条回边能到达 $subtree(p)$ 的点中 $dfsn$ 最小的值。

若 $p$ 存在一个子节点 $q$ 满足 $low(q)\ge{dfsn(p)}$，说明 $q$ 无法通过它的子树逃到比 $p$ dfs 序更小的节点。所以 $q$ 想要到达父亲节点外面的点，也就是逃出去，只能通过它的父亲节点也就是 $p$ 点，因此只要删去 $p$ 点，$q$ 和 $dfsn$ 小于 $p$ 的点就分开了，因此 $p$ 是一个割点。

那$q$是不是割点呢？不一定是。

这样一张图，有颜色的都是割点/割边（注：左边从下往上第三个点应该也是割点）。

很明显割点的父亲或儿子不一定也是割点。

两个割点之间也不一定是割边。

割边的两端也不一定是割点。

这里引入一个结论：割边两端点都是割点当且仅当去掉这条割边后得到的连通块大小都 $\ge{2}$，因为叶子不可能为割点。

所以重复一遍：$p$ 的子节点 $q$ 满足 $low(q)\ge{dfsn(p)}$，那么说明 $p$ 是割点。

还有一种特殊情况，当 $p$ 是 dfs 树的根节点时，不存在比 $p$ dfs 序更小的点。

因此对于根节点，若有两个以上子节点，那就是割点。

P3388 割点

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
vector<int> e[N];
int dfsn[N],low[N];
int cnt;
vector<int> point;
void tarjan(int p,bool root=true)
{
    int tot=0;
    low[p]=dfsn[p]=++cnt;
    for(auto &q:e[p])//枚举p的出边
    {
        if(!dfsn[q])//这个点没访问过
        {
            tarjan(q,false);//递归，并且这个点不是根
            low[p]=min(low[p],low[q]);//更新父节点的low值
            tot+=(low[q]>=dfsn[p]);//子节点的low值比父节点的dfs序还要大，那就把需要p的无法逃脱的子树个数加一
            //需要p的子树是指删去p后子树无法与外界联系
        }
        else//访问过，那就对low值取min
        {
            low[p]=min(low[p],dfsn[q]);
        }
    }
    if(tot>root)//是根那就要大于1，否则就要大于0
        point.push_back(p);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    
}

---

割边

割边，也叫做桥，定义之前说过。

较割点，修改一下$low$的定义：

• 经过以自身为根节点的子树中至多一条非树边能够到达的最小 dfs 序的点，其中非树边不包括儿子到父亲的反向边。

所以对于$low_q>dfn_p$，那么$p\leftrightarrow{q}$这条边就是桥。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
vector<int> e[N];
int dfsn[N],low[N],fa[N];
int cnt;
vector<int> point;
void tarjan_0(int p)
{
    low[p]=dfsn[p]=++cnt;
    for(auto &q:e[p])
    {
        if(!dfsn[q])
        {
            fa[q]=p;
            tarjan_0(q);
            low[p]=min(low[p],low[q]);
            if(low[q]>dfsn[p]) bridges.emplace_back(p,q);
        }
        else if(fa[p]!=q) low[p]=min(low[p],dfsn[q]);
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    
}

它和割点的区别在于它不能到它的父亲。

点双连通分量

v-DCC

是满足图中不包含任意割点的极大连通子图。

即删去任何一个点不会使这个图的连通性发生改变。

一个孤立的点是一个点双连通分量，两个割点是一个点双连通分量。

对于自环，我们特判掉即可，实际上也是一个孤立点。

对于不同的两个点双之间有且只有一个公共点，且这个点就是割点。

假如有多个公共点，那么删除任意一个公共点，两个点双之间还是可以相互连通，那么它们就可以合并为一个大的点双，因此有以上结论。

所以我们求点双连通分量也就是求每个割点的子树。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int N = 5e5 + 10;
const int M = 2e6 + 7;

int n, m, edcnt, cnt, cdcc;
int fir[N], low[N], dfsn[N];
vector<int> dcc[N];
vector<int> point;
stack<int> s;
struct Edge
{
    int to, nxt;
}e[M << 1];

void add(int u, int v)
{
    e[++edcnt].to = v;
    e[edcnt].nxt = fir[u];
    fir[u] = edcnt;
}
void tarjan(int p, bool root = true)
{
    int tot = 0;
    dfsn[p] = low[p] = ++cnt;
    s.push(p);
    if (root && fir[p] == 0)
    {
        dcc[++cdcc].emplace_back(p);
        return;
    }
    for (int i = fir[p]; i; i = e[i].nxt)
    {
        int q = e[i].to;
        if (!dfsn[q])
        {
            tarjan(q, false);
            low[p] = min(low[p], low[q]);
            if (low[q] >= dfsn[p])
            {
                tot++;
                if (tot > root) point.push_back(p);
                cdcc++;
                int top = 0;
                while (top != q)
                {
                    top = s.top();
                    s.pop();
                    dcc[cdcc].emplace_back(top);
                }
                dcc[cdcc].emplace_back(p);
            }
        }
        else low[p] = min(low[p], dfsn[q]);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        if (u == v) continue;
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i++)
        if (!dfsn[i])
            tarjan(i);
    printf("%d\n", cdcc);
    for (int i = 1; i <= cdcc; i++)
    {
        printf("%d", (int)dcc[i].size());
        for (auto &j : dcc[i])
            printf(" %d", j);
        puts("");
    }
    return 0;
}

边双连通分量

e-DCC

与点双类似，即不含割边的最大子图。

但是这个是不能通过反向边回到父亲，而重边其实属于非树边是可以走的，因此不可以通过判 $fa$ 来判断不能回到父亲，要通过判断反向边的方式。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int N = 5e5 + 7, M = 2e6 + 7;

int n, m, cnt, edcnt = 1, cdcc;
vector<int> dcc[N];
stack<int> s;
int fir[N], low[N], dfsn[N];
struct Edge
{
    int to, nxt;
}e[M << 1];

void add(int u, int v)
{
    e[++edcnt].to = v;
    e[edcnt].nxt = fir[u];
    fir[u] = edcnt;
}
void tarjan(int p, int f)
{
    low[p] = dfsn[p] = ++cnt;
    s.push(p);
    for (int i = fir[p]; i; i = e[i].nxt)
    {
        int q = e[i].to;
        if (!dfsn[q])
        {
            tarjan(q, i);
            low[p] = min(low[p], low[q]);
        }
        else if (i != (f ^ 1)) low[p] = min(low[p], dfsn[q]);
    }
    if (low[p] == dfsn[p])
    {
        int top = 0;
        cdcc++;
        while (top != p)
        {
            top = s.top();
            s.pop();
            dcc[cdcc].emplace_back(top);
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        if (u == v) continue;
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i++)
        if (!dfsn[i])
            tarjan(i, -1);
    printf("%d\n", cdcc);
    for (int i = 1; i <= cdcc; i++)
    {
        printf("%d", (int)dcc[i].size());
        for (auto &j : dcc[i])
        {
            printf(" %d", j);
        }
        puts("");
    }
    return 0;
}

练习题1

用在一条边上是最优的

枚举每条边，看看把所有花费都用在它身上能降低多少代价

如果是树边，那么直接减去

如果非树边，那就和链上最大值作差，使差值最大（也就是减小地最大）

练习题2

先求生成树中白色边最少有多少条

其次算生成树中白色边最多有多少条

也就是白边优先跑一遍 Kruscal

再黑边优先跑一边 Kruscal

如果存在一个斐波那契数处于这个最大值和最小值的区间内

那么就存在这样一颗生成树

否则不存在

因为白边最小到白边最多的过程就是一条条把黑边替换成白边的过程

练习题3

使它们差分序列$=0$

让这$m$个值相同

在差分序列中体现为前面的某个值加上x，后面的某个值减去x

在这段差分序列中，和是不变的

如果是有解的，那么首先要保证这$m$项的和等于$0$