Codeforces 732F - Tourist Reform

#图论 #技巧 #双连通分量 #边-双连通分量
Published on 2016-11-12

题目地址

描述

给定一个 n(n≤4⋅105)n(n\le 4\cdot {10}^5) 个点，m(m≤4⋅105)m(m\le 4\cdot {10}^5) 条边的联通无向图，现在你需要将无向边定向。设定向后的图中，点 ii 的 rir_i 为点 ii 能够到达的点的数量（包括 ii），请问如何将边定向，才能使 min1≤i≤nri\min_{1\le i\le n}r_i 最大？

分析

我们考虑如何将边定向，定向成 DAG 肯定是极不好的，因为 DAG 里边存在没有出度的点，而这样的话，答案就必然为 1 了。也就是说，不能出去的点，最好要形成一个环，这样答案就是环的大小了。

将图分解为若干边-双连通分量，将每个边-双连通分量看作一个点，那么此时形成了一棵缩点树。对于每个边-双连通分量，我们可以将里边的边定向，使之成为强联通分量。再将缩点后的树边定向，成为一个边指向根的树形图，这样答案就是根代表的边-双连通分量的答案，由于任意点都可以做树形图的根，所以答案就是最大的边-双连通分量的大小。

定理：答案就是是最大的边-双连通分量的大小。
证明：前面已经证明了，最大的边-双连通分量的大小是一个合法答案。现在只需证明，最大的答案不会大于最大的边-双连通分量的大小：考虑定向后的图，将其强联通缩点，答案就是没有出度的强联通分量中最小的那个，如果这个值比最大的边-双连通分量的大小更大，那么考虑将这个强联通分量中的边改为无向边，这就能形成一个边-双连通分量，而且比原图中最大的边-双连通分量的大小还要大，这就产生了矛盾。

考虑输出方案，树边是很好定向的，DFS 一下缩点树就行了。如何将边-双连通分量中的边定向，使得形成一个强联通分量呢？我们考虑直接使用 DFS 中第一次访问边的顺序，为什么？因为利用这个顺序，肯定能保证联通。我们再考虑 DFS 树，在 DFS 树中，每个点一定能通过 DFS 返祖边和非返祖边的结合，走到自己上方的点（否则存在桥，与边-双连通的定义违背），所以每个点都可以通过定向后的边走到根，自然证明这个原先的边-双连通分量通过这种定向方法后强联通。

如果不会边-双连通分量的话，上面你肯定看不懂，建议去看书学。

代码

//  Created by Sengxian on 2016/11/11.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 732F 边-双联通分量
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 400000 + 3, MAX_M = 400000 + 3;
struct edge {
    edge *next, *rev;
    int to, isCut;
    edge(edge *next = NULL, edge *rev = NULL, int to = 0, int isCut = 0, int id = 0): next(next), rev(rev), to(to), isCut(isCut) {}
} pool[MAX_M * 2], *pit = pool, *first[MAX_N];

int n, m;

int Dfs(int u, int fa) {
    static int tsp = 0, dfn[MAX_N];
    int low = dfn[u] = ++tsp;
    for (edge *e = first[u]; e; e = e->next)
        if (!dfn[e->to]) {
            int lowV = Dfs(e->to, u);
            low = min(low, lowV);
            if (lowV > dfn[u]) {
                e->isCut = true;
                e->rev->isCut = true;
            }
        } else if (e->to != fa && dfn[e->to] < dfn[u])
            low = min(low, dfn[e->to]);
    return low;    
    }

int bccCnt = 0, bccNum[MAX_N];
bool vis[MAX_N];
int dirs[MAX_M];

int Dfs(int u) {
    int cnt = 1;
    vis[u] = true, bccNum[u] = bccCnt;
    for (edge *e = first[u]; e; e = e->next)
        if (!e->isCut) {
            //直接使用 DFS 的顺序即可，每个点必然能通过定向后的边返祖，否则存在桥，与边双联通分量矛盾
            if (dirs[(e - pool) / 2] == -1) dirs[(e - pool) / 2] = (e - pool) & 1;
            if (!vis[e->to]) cnt += Dfs(e->to);
        }
    return cnt;
}

void Dfs2(int u) {
    vis[u] = true;
    for (edge *e = first[u]; e; e = e->next) {
        if (e->isCut && (dirs[(e - pool) / 2] == -1))
            dirs[(e - pool) / 2] = !((e - pool) & 1);
        if (!vis[e->to]) Dfs2(e->to);
    }
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), m = ReadInt();
    for (int i = 0, u, v; i < m; ++i) {
        u = ReadInt() - 1, v = ReadInt() - 1;
        first[u] = new (pit++) edge(first[u], NULL, v, 0, i);
        first[v] = new (pit++) edge(first[v], NULL, u, 0, i);
        first[u]->rev = first[v], first[v]->rev = first[u];
    }

    Dfs(0, -1);
    int ans = 0, idx = 0;
    memset(dirs, -1, sizeof dirs);
    for (int i = 0; i < n; ++i) if (!vis[i]) {
        int now = Dfs(i); 
        if (now > ans) idx = i, ans = now;
        bccCnt++;
    }
    memset(vis, 0, sizeof vis);
    Dfs2(idx);

    printf("%d\n", ans);
    for (int i = 0; i < m; ++i) {
        if (dirs[i] == 1) printf("%d %d\n", pool[i * 2].to + 1, pool[i * 2 + 1].to + 1);
        else if (dirs[i] == 0) printf("%d %d\n", pool[i * 2 + 1].to + 1, pool[i * 2].to + 1);
        assert(dirs[i] != -1);
    }
    return 0;
}
Codeforces 723E - One Way Reform