图论

• 1. 建图

• 2. 拓扑排序

• 3. 最短路问题

  • 1. 堆优化版dijkstra: 适用于正（其实是非负）边权

  • 2. Bellman-Ford

  • 3. SPFA:(正负都可以）

    • 1. SPFA 求最短路

    • 2. SPFA 判断是否存在负环

  • 4. floyd: 多源汇最短路

  • 5. 双端队列BFS: (只有0-1边权的最短路问题)

• 4.最小生成树问题

  • Kruskal 算法

• 5. 二分图

  • 1. 染色法判断二分图

  • 2. 二分图的最大匹配-匈牙利算法

  • 3. 最小路径重复点覆盖问题

• 6. 差分优化

• 7. 最近公共祖先（LCA)

  • 1. 倍增法

  • 2. Tarjan 离线求LCA

• 8. 连通分量

  • 1. 有向图的强连通分量

  • 2. 无向图的双连通分量

    • 1. 边的双连通分量问题

    • 2. 点的双连通分量问题

• 9. 欧拉回路与欧拉路径

1. 建图

分为邻接表 和 邻接矩阵两种 邻接表用的比较多

int n, m; // node 和 edge
int h[N], e[N], ne[N], idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

2. 拓扑排序

拓扑排序就是统计每个点的入度，入度为0的一定在前面, 遍历每个入度为0的点，把他的邻接点的入度减1， 重复这个操作就得到拓扑排序的序列了；

此外，只有有向无环图才有拓扑排序 所以也是判断有没有环的一种方式；

int n, m;
int h[N], ne[N], idx;
int q[N], d[N]; // 模拟栈 入度din

int add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++, d[b]++; // 额外统计b的入度
}
bool topsort()
{
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i++)
    {
        if(d[i] == 0) q[++tt] = i; // 入栈
    }
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            d[j]--;
            if(d[j] == 0) q[++tt] = j;
        }
    }
    // 出栈顺序 也就是拓扑排序的顺序
    return tt == n - 1;
}

3. 最短路问题

最短路问题要写的可就多了 也是趁这机会好好复习一下吧

最短路问题主要记的有以下几个方法：

堆优化dijkstra, Bellman-Ford, SPFA, Floyd; 其实还有双端队列BFS(0 - 1 边权的最短路问题), 等会也写上吧

1. 堆优化版dijkstra: 适用于正（其实是非负）边权

记住dijkstra是出栈（出队）时确定最小距离就好了

typedef pair<int, int> PII; // 距离 + 编号

int n;
int h[N], w[N], e[N], ne[N], idx;
int dist[N]; // 存储每个点 和 1 的距离
bool st[N]; // 每个点的最短距离是否已经确定

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0；
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.emplace(0, 1); 

    while(heap.size())
    {
        PII t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        // 记住了 dijkstra是在出队确定 
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.emplace(dist[j], j);
            }
        }
    }

    if(dist[n] = 0x3f3f3f3f) return -1;
    else return dist[n];
}
memset(h, -1, sizeof h);

2. Bellman-Ford

现在看来， Bellman-Ford 算法最适合解决的问题是有边数限制的最短路问题 剩下比如有负权边的最短路问题，负环的判断等等都可以用SPFA来解决

int n, m;
int dist[N];

struct Edge
{
    int a, b, w;
}edges[M];

int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n; i++) // 在这里 这里的循环次数就是边数限制
        for(int j = 0; j < m; j++)
        {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            if(dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    // 注意这里的判断
    if(dist[n] > 0x3f3f3f3f / 2)
        return -1;
    return dist[n];
}

3. SPFA:(正负都可以）

spfa 的代码其实和堆优化dijkstra很像 因为都是用堆去优化那个找当前最小距离的过程;

这两个的判断条件不一样 要记清:

• dijkstra 是出队就保证最短距离

• 但是spfa是出队都没有办法保证是最短距离，只要更新就要入栈，st数组的意义在于如果栈中有这个元素就不必再次加入了（因为肯定是要重算）

1. SPFA 求最短路

int n;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];

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;
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > w[i] + dist[t])
            {
                dist[j] = w[i] + dist[t];
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}

2. SPFA 判断是否存在负环

相较于求最短路 额外围护一个cnt数组，这个数组记录最短路径的节点数量 只要超过 n + 1 则证明必有负环存在

注意这里要把所有点都加入队列，dist清空or not 都无所谓 避免起点与负环不连通-> 找不到

找正环 : 把求最短路变成求最长路即可！

常用于0-1分数规划问题

除了这个之外还有个额外的trick，如果超时了的话 可以按照spfa出栈元素的次数判断是否存在负环 如果出栈元素的次数大于一个经验值（可以试一试 2*n 3*n）就可以当成有负环了

int n;
int h[N], e[N], w[N], ne[N], idx;
int dist[N], cnt[N];
bool st[N];

bool spfa()
{
    memset(dist, 0, sizeof dist);
    queue<int> q;
    for(int i = 1; i <= n; i++)
    {
        q.push(1);
        st[1] = true;
    }
    while(q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;
        for(int i = h[t]; ~i; 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;
                if(cnt[j] >= n) return true;
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

4. floyd: 多源汇最短路

基于动态规划 记住那三重循环的顺序 先遍历的是中间点k

    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;

// 算法结束后，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]);
}

同样的 可以将floyd退化为bool值 这样直接判断是否连通

5. 双端队列BFS: (只有0-1边权的最短路问题)

对于只有0 - 1 两种边权的最短路问题，可以用双端队列广搜来实现 不必维护一个heap;

int bfs()
{
    memset(st, false, sizeof st);
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    deque<int> q;
    q.push_back(1);

    while(q.size())
    {
        int t = q.front();
        q.pop_front();
        if(st[t]) continue;
        st[t] = true;

        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] < dist[t] + w[i]) // 这里w[1] 只会取0 1
            {
                dist[j] = dist[t] + w[i];
                if(w[i]) q.push_back(j);
                else     q.push_front(j);
            }
        }
    }
    return dist[n];
}

4.最小生成树问题

最小生成树就记一个Kruskal算法就好；

Kruskal 算法

Kruskal算法基于的是并查集，整体思路很简单, 将所有边按权重从小到大排序，枚举所有边(a, b, w) 如果 a b尚未连通，就将这条边加入集合中 并统计权重就好了；

struct Edge
{
    int a, b, w;
    bool operator<(const Edge& e) const
    {
        return this->w < e.w;
    }
}edges[2 * N];

int p[N];

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

// 并查集初始化
for(int i = 1; i <= n; i++)
    p[i] = i;

// 读入edges
...
int res = 0, cnt = 0;
for(int i = 0; i < n; i++)
{
    int a = edges[i].a, b = edges[i].b, w = edges[i].w;
    if(find(a) != find(b))
    {
        p[find(a)] = find(b);
        res += w;
        cnt++;
    }
}

// 最小生成树 n个点连通一定是n - 1 条边 这也是连通性判断的一个依据
if(cnt < n - 1) puts("impossible");
else printf("%d\n", res);

对于Kruskal算法而言 可以只求前一半 - 最小生成森林 / 后一半 - 缩点的最小生成树 都是可以的；

有这样两个性质： - 最小生成树的边数一定是n - 1 - 得到的解不仅是边权和最小，最大边权也最小

5. 二分图

二分图这一块有判断是否是二分图（染色法） 和 二分图的最大匹配（匈牙利算法）两块；

具体细分而言

• 匈牙利算法： 匹配 最大匹配 匹配点 增广路径

• 最小点覆盖 最大独立集 最小路径点覆盖 最小路径重复点覆盖问题

  • 公式：最大匹配数 = 最小点覆盖 = 总点数 - 最大独立集 = 总点数 - 最小路径覆盖

1. 染色法判断二分图

一个图是二分图 等价于 图中没有奇数环

染色法判断二分图的实质就是DFS；一个边连接的两个点不会是同一个颜色

0 - 未染色 1 - 颜色1 2 - 颜色2

bool is_bi_graph()
{
    for(int i = 1; i <= n; i++)
        if(!color[i])
            if(!dfs(i, 1)) return false;
    return true;
}

bool dfs(int a, int c)
{
    color[a] = c;
    for(int i = h[a]; ~i; 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;
}

2. 二分图的最大匹配-匈牙利算法

这个要好好背一下；

int n1, n2; // n1 表示第一个集合中的点数 n2 表示第二个
int h[N], e[M], ne[M], idx; // 匈牙利算法只用存集合1到集合2的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点
bool st[N]; // 存储第二个集合中的每个点是否被当前点遍历过

bool find(int x)
{
    for(int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true;
            if(match[j] == 0 || find(match[j])) // j还未匹配 或者 之前匹配的可以匹配其他人
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int res = 0;
for(int i = 1; i <= n1; i++)
{
    memset(st, false, sizeof st);
    if(find(i)) res++;
}

3. 最小路径重复点覆盖问题

方法：

• 1. 求原图的传递闭包

• 1. 原图的最小路径重复点覆盖 = 新图的最小路径覆盖 = 新图的 n - 最大匹配

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

// 传递闭包

const int N = 210, M = 30010;

int n, m;
bool g[N][N], st[N];
int match[N];

bool find(int x)
{
    for(int i = 1; i <= n; i++)
    {
        if(g[x][i] && !st[i])
        {
            st[i] = true;
            if(match[i] == 0 || find(match[i]))
            {
                match[i] = x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d", &n, &m);
    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = true;
    }
    // 传递闭包
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                g[i][j] = g[i][j] || (g[i][k] && g[k][j]);
    int res = 0;
    // 拆点 * 不必了 g直接当成 x -> x'
    for(int i = 1; i <= n; i++)
    {
        memset(st, false ,sizeof st);
        if(find(i)) res++;
    }
    cout << n - res << endl;
    return 0;
}

6. 差分优化

...

7. 最近公共祖先（LCA)

LCA问题：在一个有根树中，最近的公共祖先（自己也算）

1. 倍增法

方法如下：

• 预处理：fa[i, j]表示从i开始 向上走2^j步所到达的节点

• 预处理：depth[i]表示i节点所在的深度

• 查询： 求lca(a, b)

  • 如果a的深度比b大 -> 先跳到同一层

  • 保证在同一层下，共同向上跳，直到跳到LCA的下面一层

大概的框架就是这样，此外在代码实现上还有许多细节（比如哨兵节点0的应用等等）

depth显然用dfs bfs都可以，而fa[i,j] 可以用递推求解 fa[i, j] = fa[fa[i, j - 1], j - 1] （爸爸的爸爸是爷爷）

倍增法求LCA的复杂度：预处理o(nlogn) 查询一次：o(logn)

int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16]; // 这里16是 log(最大深度)

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 预处理深度 -> dfs bfs都行
void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    // 哨兵节点 0 指代所有空集的情况
    depth[0] = 0, depth[root] = 1;
    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(depth[j] > depth[t] + 1)
            {
                q.push(j);
                depth[j] = depth[t] + 1;
                fa[j][0] = t;
                for(int k = 1; k <= 15; k ++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}
int lca(int a, int b)
{
    if(depth[a] < depth[b]) swap(a, b);
    for(int k = 15; k >= 0; k--)
    {
        // 哨兵的好处1假如跳出去了，那么depth[a][k] = 0 < depth[b]
        if(depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    }
    if(a == b) return a;
    for(int k = 15; k >= 0; k--)
    {
        // 哨兵的好处2假如两个点都跳出去，那么f[a][k] = f[b][k] = 0 ，就不会执行。
        // 此外 跳到同一层不能判断是最近祖先（可能比LCA还高) 所以要到下一层才行
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
    
}

2. Tarjan 离线求LCA

这一定要上图了

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int p[N]; // 并查集
int res[N]; // 查询返回值
int st[N]; // tarjan 保留编号
vector<PII> query[N]; // first 是查询的第二个点 second 是查询的编号
 
int find(int x)
{
    if(p[x] != x) 
        p[x] = find(p[x]);
    return p[x];
}

void tarjan(int u)
{
    st[u] = 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            tarjan(j);
            p[j] = u;
        }
    }
    // 回溯
    for(auto item : query[u])
    {
        int y = item.first, id = item.second;
        if(st[y] == 2)
        {
            int anc = find(y); // 找到并查集的root 即为u 和 y的LCA
        }
    }
    st[u] = 2;
}

// 把query 存储起来
int a, b;
if(a != b)
{
    query[a].emplace_back(b, i);
    query[b].emplace_back(a, i);
}
tarjan(...)；

8. 连通分量

1. 有向图的强连通分量

tarjan缩点

int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, sz[N];
void tarjan(int u)
{
    low[u] = dfn[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(in_stk[j])
        {
            low[u] = min(low[u], dfn[j]);
        }
    }
    // u是该强连通分量的top
    if(dfn[u] == low[u])
    {
        int y;
        ++scc_cnt;
        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            sz[scc_cnt]++;
        }while(y != u);
    }
}
// 在外面
for(int i = 1; i <= n; i++)
{
    if(!dfn[i])
        tarjan(i);
}

此外 还有些额外的结论

• id的倒序 就是DAG的拓扑排序

• 设DAG的入度为0点数量为p 出度为0点的数量为q 则使得整个图为强连通量 最少需要添加的边数为max(p, q)

2. 无向图的双连通分量

无向图的双连通分量分为两种：

• 边的双连通分量 e_dcc: 不含桥的连通分量

• 点的双连通分量 v_dcc: 不含割点的连通块

1. 边的双连通分量问题

和有向图的强连通分量求法类似，也是引入一个时间戳的概念 维护dfn 和 low两个时间戳数组

如何找到桥？ x -> y dfn[x] < low[y]

如何找到所有边的双连通分量？ 用一个栈帮助找到连通分量内的所有点

桥(割边) 对于一个无向连通图来说, 如果我们删除一条边之后, 图变得不再连通了, 那么我们九讲这条边称为桥.

定义 一个极大的(图中不存在任何一个非连通块中的点加入连通块之后, 该连通块依然是连通块)不包含桥的连通块

性质 对于一个边连通分量来说, 我们不管删除连通分量的哪一条边, 它都是连通的. 对于一个边连通分量来说, 任意两点之间至少包含两条不相交的路径(两条路径上无公共边) 这是一个充要条件

tarjan算法求边双连通分量

无向图不存在横叉边

因为双向不存在后面能到前面, 前面不能到后面的情况, 那么如果存在后面连到前面的一条边, 那么dfs序遍历的时候, 我们就已经将后面的点遍历到了, 就不可能再后面再遍历到后面那个点了.

时间戳 dfn[u]: 遍历到当前节点的编号 low[u]: 不经过走过来的那条边(父边)能走到的最小编号节点

判断桥 对于x, y之间的一条边, 如果low[y]能到x的祖先节点, 那么就不是桥, 若low[y] = y, 即是桥 dfn[x]<low[y](严格小于)

找e-dcc代码思路:

1. 将所有的桥删掉剩下的都是边连通分量了

2. 用栈存储搜到的所有点, 当搜到一个点的dfn[x] == low[x], 即这个点上面的一条边就为桥, 将栈中所有点标记即可

找e-dcc代码模板:

void tarjan (int u, int f) // f是u这个点由哪条边过来的, 哪条边的序号
{
    dfn[u] = low[u] = ++ timestamp;
    st[++ tt] = u;

    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if(dfn[u] < low[j]) // 等于也不是桥
                is_bridge[i] = is_bridge[i ^ 1] = 1; // 蓝书位运算的操作
        }
        else if(i != f ^ 1) // 不经过父边 必定不是桥 是边连通分量, 无需判重数组
            low[u] = min(low[u], dfn[j]);
    }

    if(dfn[u] == low[u]) // 第一个非边双连通分量中的点是入了栈的
    {
        int y;
        dcc_cnt ++ ;

        do
        {
            y = st[tt -- ];
            id[y] = dcc_cnt;
        }while(y != u);
    }
}

2. 点的双连通分量问题

点双连通分量

割点 每一个割点都至少属于两个连通分量 对于一个无向连通图来说, 如果我们删除某个点之后, 该连通图不连通了, 那么我们就称其为该联通图的割点.

定义 一个极大的不包含割点的连通块 tarjan算法求点双连通分量

时间戳 dfn[u]: 意义同边双连通分量 low[u]: 每个顶点在不经过父节点的情况下能到的最小编号顶点, 如果low[u]大于等于dfn[father] (就是不能到已经遍历过的点, 即father的祖先节点), father为割点.

判断(找)割点

// cc_cnt: 连通分量的数量, 而非点双
void tarjan(int u) // 找割点和所有连通分量(找子连通分量, 这种找法补不重不漏)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u;

    if (u == root && h[u] == -1) // 无边节点, 单点v-dcc
    {
        cc_cnt ++ ;
        cc[cc_cnt].push_back(u);
        return;
    }

    int cnt = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
            if (dfn[u] <= low[j]) // 对于根节点来说, 这个是必然满足的  把所有以u为根节点的子连通块全部存下来  不能不通过这个点到u的祖先节点, 则u就是这个连通分量的割点
            {
                cnt ++ ; // 儿子数量
                if (u != root || cnt > 1) cut[u] = true; // 1. 不是根节点, 2. 是根节点, 要有两个儿子才是割点
                ++ cc_cnt; // 我们待会儿通过连通块中割点的个数判断点双连通分量
                int y;
                do 
                {
                    y = stk[top -- ];
                    cc[cc_cnt].push_back(y);
                } while (y != j); // 如果写成y != u, 由于一个点可能属于多个v-dcc, 则u被第一个cc弹出之后, 后面的cc就永远没有u这个点了就会死循环. (后面单独加上)
                cc[cc_cnt].push_back(u); // u点也是该cc的一部分
            }
        }
        else low[u] = min(low[u], dfn[j]); // 无需vis判重数组的原因: 由于在有向图的强连通分量中, u能走到的点, 不一定是属于该SCC(因为该点不一定就能到u), 只有在栈中的才属于, 而无向图能走到的点就一定属于当前连通块
    }
}

void find ()
{
    for (int i = 1; i <= cc_cnt; i ++ )
    {
        int cnt = 0;
        for (int j = 0; j < cc[i].size(); j ++ )
            if (cut[cc[i][j]]) // 割点数组
                cnt ++ ;

        if (cnt == 0) // 割点为0就是v-dcc
        {
            cout << i << endl;
        }
        else puts("No V-dcc");
    }
}

9. 欧拉回路与欧拉路径

算法会简单一些hhh

背景：哥尼斯堡七桥问题 / 一笔画问题

欧拉路径 给定一张无向图，若存在一条从节点 S 到节点 T 的路径，恰好不重不漏地经过每条边一次(可以重复经过图中的节点)，则称该路径为 S 到 T 的欧拉路。

欧拉回路 若存在一条从节点 S 出发的路径，恰好不重不漏地经过每条边一次(可以重复经过图中的节点)，最终回到起点 S，则称该路径为欧拉回路。

定义一下：

• 入度(din)：进入该点的边的数量。

• 出度(dout)：走出该点的边的数量。

• 度(deg)：每个点的 入度 + 出度。

• 奇结点（奇顶点）：连接该结点的边的数量为奇数

• 偶结点（偶顶点）：连接该结点的边的数量为偶数

判断依据：

1. 对于无向图，所有边都是连通的

   • 存在欧拉路径的充分必要条件：度数为奇数的点只能有0 or 2个

   • 存在欧拉回路的充分必要条件：度数为奇数的点只能有0个

2. 对于有向图，所有边都是连通的

   • 存在欧拉路径的充分必要条件：

     • 要么所有点的出度等于入度

     • 要么除了两个点之外，所有点的出度等于入度，并且满足剩下的两个点 ：一个出度比入度多1（起点）一个入度比出度多1（终点）

   • 存在欧拉回路的充分必要条件：所有点的出度均等于入度

求欧拉回路 注意这里的删边优化

1. dfs搜索

2. 在递归搜索结束后加入答案序列

3. 最后的欧拉回路是答案序列的倒序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 400010;

int type;
int n, m;
int h[N], e[M], ne[M], idx;
bool used[M];
int ans[M], cnt;
int din[N], dout[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    for (int &i = h[u]; ~i;)
    {
        if (used[i])
        {
            i = ne[i];
            continue;
        }

        used[i] = true;
        if (type == 1) used[i ^ 1] = true;

        int t;

        if (type == 1)
        {
            t = i / 2 + 1;
            if (i & 1) t = -t;
        }
        else t = i + 1;

        int j = e[i];
        i = ne[i];
        dfs(j);

        ans[ ++ cnt] = t;
    }
}

int main()
{
    scanf("%d", &type);
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        if (type == 1) add(b, a);
        din[b] ++ , dout[a] ++ ;
    }

    if (type == 1)
    {
        for (int i = 1; i <= n; i ++ )
            if (din[i] + dout[i] & 1)
            {
                puts("NO");
                return 0;
            }
    }
    else
    {
        for (int i = 1; i <= n; i ++ )
            if (din[i] != dout[i])
            {
                puts("NO");
                return 0;
            }
    }

    for (int i = 1; i <= n; i ++ )
        if (h[i] != -1)
        {
            dfs(i);
            break;
        }

    if (cnt < m)
    {
        puts("NO");
        return 0;
    }

    puts("YES");
    for (int i = cnt; i; i -- ) printf("%d ", ans[i]);
    puts("");

    return 0;
}

输出字典序最小的路径 : 按照字典序来搜