第二节 Tarjan

Contents

强连通分量

题目:P3387 缩点

题目大意:

给定一个 n 个点 m 条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。

分析:

先使用 tarjan 缩点,然后对图进行重构,再对拓扑图记忆化搜索。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 50;
const int M = 1e5 + 50;
int a[M], b[M], x[N];
int n, m;
int ans;

int head[N], tot;
struct Edge {
    int nex, to;
}e[M];
void add(int a, int b) {
    e[++tot] = {head[a], b};
    head[a] = tot;
}

int dfn[N], low[N], in[N], sum;
int bel[N], col;
int g[N], f[N];
stack<int> s;
void tarjan(int u) {
    dfn[u] = low[u] = ++sum;
    s.push(u); in[u] = 1;
    for (int i = head[u]; i; i = e[i].nex) {
        int to = e[i].to;
        if (!dfn[to]) {
            tarjan(to);
            low[u] = min(low[u], low[to]);
        }
        else if (in[to]) {
            low[u] = min(low[u], dfn[to]);
        }
    }
    if (low[u] == dfn[u]) {
        col++;
        do {
            bel[u] = col;
            u = s.top(); s.pop();
            in[u] = 0;
        }
        while (low[u] != dfn[u]);
    }
}

void search(int u) {
    if (f[u]) return;
    f[u] = g[u];
    int maxson = 0;
    for (int i = head[u]; i; i = e[i].nex) {
        int to = e[i].to;
        search(to);
        maxson = max(maxson, f[to]);
    }
    f[u] += maxson;
}

void rebuild() {
    memset(head, 0, sizeof(head));
    tot = 0;
    for (int i = 1; i <= m; i++) {
        if (bel[a[i]] != bel[b[i]]) {
            add(bel[a[i]], bel[b[i]]);
        }
    }
    for (int i = 1; i <= n; i++) {
        g[bel[i]] += x[i];
    }
    for (int i = 1; i <= col; i++) {
        if (!f[i]) search(i);
        ans = max(ans, f[i]);
    }
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
        add(a[i], b[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    rebuild();
    cout << ans << "\n";
    return 0;
}

双连通分量

P2860 [USACO06JAN]Redundant Paths G

题目大意:

给你一个 n 个点 m 条边的无向图,问至少要加几条边,才可以使得任意两点间有至少两条不同的路径。

分析:

用 tarjan 求出双连通分量,得到了一颗树。树的叶子结点数 / 2 向上取整即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 50;
const int M = 2e4 + 50;
int n, m;
int a[M], b[M];
int ans;

int head[N], tot = 1; // 和网络流一样,初始化为1
struct Edge {
    int nex, to;
}e[M];
void add(int a, int b) {
    e[++tot] = {head[a], b};
    head[a] = tot;
}

int dfn[N], low[N], in[N], sum;
int bel[N], col;
int vis[M];
int degree[N];
stack<int> s;
void tarjan(int u) {
    dfn[u] = low[u] = ++sum;
    s.push(u);
    in[u] = 1;
    for (int i = head[u]; i; i = e[i].nex) {
        if (vis[i]) continue;
        int to = e[i].to;
        vis[i] = vis[i ^ 1] = 1; // 记录正反边
        if (!dfn[to]) {
            tarjan(to);
            low[u] = min(low[u], low[to]);
        }
        else if (in[to]) {
            low[u] = min(low[u], dfn[to]);
        }
    }
    if (low[u] == dfn[u]) {
        col++;
        do {
            bel[u] = col;
            u = s.top(); s.pop();
            in[u] = 0;
        }
        while (low[u] != dfn[u]);
    }
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
        add(a[i], b[i]);
        add(b[i], a[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= m; i++) {
        if (bel[a[i]] != bel[b[i]]) {
            degree[bel[a[i]]]++;
            degree[bel[b[i]]]++;
        }
    }
    for (int i = 1; i <= col; i++) {
        if (degree[i] == 1) {
            ans++;
        }
    }
    cout << (ans + 1) / 2 << "\n";
    return 0;
}

割点

题目大意:

给出一个 n 个点,m 条边的无向图,求图的割点。在无向连通图中,如果将其中一个点以及所有连接该点的边去掉,图就不再连通,那么这个点就叫做割点。

分析:

对于根节点,计算其子树数量,如果有 2 棵即以上的子树,就是割点。因为如果去掉这个点,这两棵子树就不能互相到达。

对于非根节点,有边 (u, v),如果 low[v]\ge dfn[u],此时 u 就是割点。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 50;
const int M = 2e5 + 50;
int n, m;
int ans;

int head[N], tot;
struct Edge
{
    int nex, to;
}e[M];
void add(int a, int b) {
    e[++tot] = {head[a], b};
    head[a] = tot;
}

int dfn[N], low[N], sum;
int iscut[N];
void tarjan(int u, int rt) {
    int cnum = 0;
    dfn[u] = low[u] = ++sum;
    for (int i = head[u]; i; i = e[i].nex) {
        int to = e[i].to;
        if (!dfn[to]) {
            tarjan(to, rt);
            low[u] = min(low[u], low[to]);
            if (low[to] >= dfn[u] && u != rt) {
                iscut[u] = 1;
            }
            if (u == rt) {
                cnum++;
            }
        }
        else {
            low[u] = min(low[u], dfn[to]);
        }
    }
    if (u == rt && cnum >= 2) {
        iscut[u] = 1;
    }
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1, a, b; i <= m; i++) {
        cin >> a >> b;
        add(a, b); add(b, a);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i, i);
    }
    for (int i = 1; i <= n; i++) {
        if (iscut[i]) ans++;
    }
    cout << ans << "\n";
    for (int i = 1; i <= n; i++) {
        if (iscut[i]) {
            cout << i << " ";
        }
    }
    cout << "\n";
    return 0;
}

2-SAT

题目:P4782 【模板】2-SAT 问题

题目大意:

n 个布尔变量 x_1\sim x_n,另有 m 个需要满足的条件,每个条件的形式都是 「x_itrue / falsex_jtrue / false」。比如 x_1 为真或 x_3 为假、x_7 为假或 x_2为假。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

第一行两个整数 nm,意义如题面所述。接下来 m 行每行 4 个整数 i, a, j, b,表示 x_iax_jb (a, b\in {0,1})

如无解,输出 IMPOSSIBLE;否则输出 POSSIBLE。下一行 n 个整数 x_1\sim x_nx_i\in{0,1}),表示构造出的解。

// a, b 都真,-a -> b, -b -> a
// a 假 b 真,a -> b, -b -> -a
// a 真 b 假,-a -> -b, b -> a
// a, b 都假,a -> -b, b -> -a
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e6 + 50;
vector<int> g[N];
int n, m;
int dfn[N], low[N], in[N], sum;
int bel[N], col;
stack<int> s;
void tarjan(int u) {
    dfn[u] = low[u] = ++sum;
    s.push(u); in[u] = 1;
    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (in[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        col++;
        do {
            bel[u] = col;
            u = s.top(); s.pop();
            in[u] = 0;
        }
        while (low[u] != dfn[u]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, xa, b, xb;
        cin >> a >> xa >> b >> xb;
        // x 点标号为 x,-x 标号为 x+n
        g[a + n * (xa & 1)].pb(b + n * (xb ^ 1));
        g[b + n * (xb & 1)].pb(a + n * (xa ^ 1));
    }
    for (int i = 1; i <= (n << 1); i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        if (bel[i] == bel[i + n]) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }
    cout << "POSSIBLE\n";
    for (int i = 1; i <= n; i++) {
        cout << (bel[i] < bel[i + n]) << " ";
    }
    cout << "\n";
    return 0;
}

例题:Gym 101987(2018 ICPC Seoul)K. TV Show Game

题目大意:

有一个字符串长度为 k,每个位置只包含字符 R 或者 B,现在有 n 个人,每个人都有 3 个猜想,问能否构造出一种字符串,使得满足每个人正确的猜想数都大于等于 2.

分析:

假设猜测的三个位置分别是 p1,p2,p3,那么就可以推出六条关系。

  • $p1$ 错误 -> $p2$ 正确,
  • $p1$ 错误 -> $p3$ 正确,
  • $p2$ 错误 -> $p1$ 正确,
  • $p2$ 错误 -> $p3$ 正确,
  • $p3$ 错误 -> $p1$ 正确,
  • $p3$ 错误 -> $p2$ 正确,
// R:x+n B:x
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b, c, A, B, C; char x, y, z;
        scanf("%d %c%d %c%d %c", &a, &x, &b, &y, &c, &z);
        A = (x == 'R'), B = (y == 'R'), C = (z == 'R');
        /*
          g[a + n * A] 表示 p1 正确,则 g[a + n * (A ^ 1)] 表示 p1 错误
        */
        g[a + n * (A ^ 1)].push_back(b + n * B);
        g[a + n * (A ^ 1)].push_back(c + n * C);
        g[b + n * (B ^ 1)].push_back(a + n * A);
        g[b + n * (B ^ 1)].push_back(c + n * C);
        g[c + n * (C ^ 1)].push_back(a + n * A);
        g[c + n * (C ^ 1)].push_back(b + n * B);
    }
    for (int i = 1; i <= (n << 1); i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        if (bel[i] == bel[i + n]) {
            printf("-1\n"); return 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        printf(bel[i] < bel[i + n] ? "B" : "R");
    }
    puts("");
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇