图论问题常见算法（一）

Euler 回路

不难发现，在欧拉回路中，进和出应该是对应的，也就是说，除了起点和终点外，其他点的进出次数应该相等

无向图
奇点，一个点的 $\textbf{deg}(u)$ （即度数）为奇数

1. 如果一个无向图是连通的，且最多只有 $2$ 个奇点，一定存在欧拉回路
2. 如果有 $2$ 个奇点，必须是一个奇点为起点，另一个为终点
3. 如果奇点不存在，从任意点 $u$ 出发，一定会回到 $u$，称为欧拉回路

有向图
当然前提是有向图必须是连通的

1. 最多只能有两个点的入度不等于出度，并且起点的 $\text{outdeg}(u) = \text{indeg}(u) + 1$
   终点 $\text{indeg}(u) = \text{outdeg}(u) + 1$

代码模版，用 $\text{vis}(u, v)$ 标记边是否被访问过

stack<PII> stk;
void euler(int u) {
    for (int v = 0; v < n; v++) if (G[u][v] && !vis[u][v]) {
        vis[u][v] = vis[v][u] = 1;
        euler(v);
        stk.push(PII(u, v));
    }
}

Play On Words
大意是给你一些单词，判断是否存在一种排列，使得每个单词的第一个字母和上一个单词的最后一个字母相同

• 不难想到先用并查集，将每个单词的第一个字母 $u$ 和最后一个字母 $v$ 抽出来，则每个单词对应
  $(u, v)$ 这个有向边，可以先使用并查集判连通
  初始化连通块数量 $cc = n$，执行并查集合并的时候，$cc-=1$，只有 $cc = 1$ 的时候才是合法情况
• 那么问题抽象称为，是否存在一种方案，使得每个单词恰好只使用 $1$ 次
  也就是对应欧拉路径中，每条边恰好只经过一次，那么当且仅当存在欧拉路径的时候，问题有解
• 有向图的欧拉路径，入度 $\text{deg}(u)++$，出度 $\text{deg}(u)--$
  这样欧拉回路的判定条件简化为，最多只有两个点 $\text{deg}(u) \neq 0$
  并且其中一个点 $\text{deg}(u) = -1$ 作为起点，另一个点 $\text{deg}(u) = 1$ 作为终点
  对于有向边 $(u, v)$，$\text{deg}(v)++, \text{deg}(u)--$

const int maxn = 1e5 + 10;
char str[maxn];
int n, cc = 26;
int deg[27], pa[27], vis[27];

inline int get(int x) {
    return pa[x] == x ? x : pa[x] = get(pa[x]);
}

void init() {
    cc = 26;
    memset(vis, 0, sizeof vis);
    memset(deg, 0, sizeof deg);

    for (int i = 0; i < 26; i++) pa[i] = i;
}

void solve() {
    vector<int> res;

    for (int i = 0; i < 26; i++) {
        if (deg[i] != 0) res.push_back(deg[i]);
    }
    sort(res.begin(), res.end());
    //debug(res[0]);

    if (res.empty()) {
        puts("Ordering is possible.");
        return;
    }

    if (res.size() == 2 && res[0] == -1 && res[1] == 1) {
        puts("Ordering is possible.");
        return;
    }

    puts("The door cannot be opened.");
    return;
}


int main() {
    freopen("input.txt", "r", stdin);
    int cas;
    cin >> cas;

    while (cas--) {
        // init
        init();
        
        scanf("%d", &n);

        for (int i = 0; i < n; i++) {
            scanf("%s", str);

            int u = str[0] - 'a', v = str[strlen(str)-1] - 'a';
            vis[u] = vis[v] = 1;
            deg[v]++, deg[u]--;

            u = get(u), v = get(v);
            if (u != v) {
                pa[u] = v;
                cc--;
            }
        }

        // then solve
        for (int i = 0; i < 26; i++) if (!vis[i]) cc--;

        if (cc != 1) {
            puts("The door cannot be opened.");
            continue;
        }

        // euler path
        solve();
    }
}

Euler 回路有关的构造

Min Cost String
题意大致是构造字符串，使得代价最小
定义代价为，$1 \leqslant i < j \leqslant n$，满足 $S[i] = S[j] \ \textbf{and} \ S[i+1] = S[j+1]$
需要构造的字符串长度为 $n$，一共可以使用 $k \in [1, 26]$ 个不同的小写字母

1. 首先很容易想到，如果 $n$ 很小，而 $k$ 很大 $(k=26)$ 的情况，只需要依次使用不同的字母 $c$ 构造即可
2. 可以发现随着 $n$ 增加，一定会产生重复代价，假设我们构造了 $S[i] = u, S[i+1] = v$
   那么存在一个位置 $j$ 满足 $S[j] = u, S[j+1] = v$，需要让这个重复代价尽可能小
3. 也就是说，一开始需要构造尽可能不同的二元组 $(u, v)$，并且保证 $(u, v)$ 只出现一次
   如果在 $S[i]$ 处出现 $(u, v)$，在 $S[j]$ 中也出现 $(u, v)$，那么有 $S_i = S_j, S_{i+1} = S_{j+1}$
   会产生额外代价
   一开始的时候尽量满足 $(u, v)$ 只用一次，实际上就是找一条欧拉路径
   而尽量不同的二元组 $(u, v)$，可以在 $k$ 个点的完全图上遍历
4. $k$ 个点的完全图有 $k^2$ 条边，每条边 $(i, j)$ 都出现 $2$ 次，所以完全图没有奇点
   注意，这里无向图转为有向图，$(u, v)$ 无向边看成是 $u \to v$ 和 $v \to u$，这样构造就没有奇点
   没有奇点的图一定存在欧拉路径，并且从任意一点开始 $\text{dfs}$，一定会回到这个点 （也就是开始重复）
   所以在 $k^2 < n-1$ 的情况下，一定会产生重复代价
   假设构造出 $S_i = u$，那么欧拉路径第 $m$ 次到达 $u$ 时，满足
   $\displaystyle S_i = S_{i+n} = S_{i+2n} = \cdots S_{i+(m-1)n} = u$
   对于边 $(u, v)$，只在欧拉路径回到 $u$ 这个点时产生代价，每一次走欧拉回路时，$(u, v)$ 只出现一次
   所以这个代价最小

const int maxn = 27;
int n, k;
int G[maxn][maxn], vis[maxn][maxn];
vector<int> path;

void build() {
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++)
            G[i][j] = 1;
    }
}

void dfs(int u) {
    for (int v = 0; v < k; v++) {
        if (G[u][v] && vis[u][v] == 0) {
            vis[u][v] = 1;
            dfs(v);
            path.push_back(v);
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> k;

    // build
    memset(vis, 0, sizeof vis);
    build();

    dfs(0);
    string res = "";
    for (int i = 0; i < n; i++) {
        int id = i % path.size();
        res += string(1, (char)('a' + path[id]));
    }
    cout << res << endl;
}

拓扑排序和 DAG

DAG 相关的问题，很容易让人想到拓扑排序

构造有向无环图

1. 如果仅考虑有向边构成的有向连通块 $G'(V', E')$，那么问题很容易解决
   只需要对 $G'$ 进行拓扑排序，队列中元素个数恰好等于 $V'$，那么存在拓扑序
   否则不存在拓扑序
2. 考虑整个图 $G$，如果仅加入有向边 $E'$，那么有向连通块 $G'$ 之外的离散点 $u$
   其入度满足 $\text{deg}(u) = 0$，这些点仍然可以进拓扑队列，存在拓扑序
3. 实际上将有向连通块 $G'$ 缩点成 $U$，实际上 $U$ 为 $G'$ 的 $\text{dfs}$ 树的根
   对于 $U$ 之外的离散点 $u_i$，由于他们的 $\text{deg}(u_i) = 0$
   这些点一开始就会进入拓扑队列中，必然能够构造出 DAG 如下
   $G = \{u_0 \to u_1 \to \cdots \to U \to \cdots u_k \}$
   如果 $U$ 是一个 DAG，那么 $G$ 也是一个 DAG
4. 具体来说，一开始只加入有向边，对于有向边之外的离散点，初始化 $\text{deg}(u) = 0$
   然后将所有 $\text{deg}(u) = 0$ 的点放入拓扑队列中，并执行拓扑排序
   类似 $\text{tarjan}$ 算法，拓扑序即拓扑队列中出队顺序
   定义一个 $\text{dfn}(u)$ 记录节点 $u$ 出队列的时间戳
5. 对于未指定方向的边 $(x, y)$，拓扑排序后，只需要从 $\text{dfn}$ 小的点指向大的点

const int maxn = 2e5 + 10, maxm = 2e5 + 10;
int n, m;

int head[maxn], ver[maxm], ne[maxm], idx = 1, deg[maxn], dfn[maxn], num = 0;

class Edge {
public:
    int a, b;
    Edge(int a = 0, int b = 0) : a(a), b(b) {}
};

vector<Edge> edges, e;

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

bool topo() {
    queue<int> que;
    for (int u = 1; u <= n; u++) if (deg[u] == 0) que.push(u);

    while (que.size()) {
        auto x = que.front(); que.pop();
        dfn[x] = ++num;

        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (--deg[y] == 0) que.push(y);
        }
    }

    return num == n;
}

void solve() {
    for (auto x : e) {
        printf("%d %d\n", x.a, x.b);
    }
    for (auto x : edges) {
        int u = x.a, v = x.b;
        if (dfn[u] > dfn[v]) swap(u, v);
        printf("%d %d\n", u, v);
    }
}

void init() {
    memset(head, 0, (n+1) * 4);
    memset(deg, 0, (n+1) * 4);
    memset(dfn, 0, (n+1) * 4);
    idx = 1, num = 0;
    edges.clear(), e.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    int cas;
    cin >> cas;

    while (cas--) {
        scanf("%d%d", &n, &m);
        init();

        while (m--) {
            int t, a, b;
            scanf("%d%d%d", &t, &a, &b);

            if (t) {
                add(a, b);
                deg[b]++;
                e.push_back(Edge(a, b));
            }
            else edges.push_back(Edge(a, b));
        }

        if (!topo()) {
            puts("NO");
            continue;
        }
        puts("YES");
        solve();
    }
}