强连通分量 2-SAT
Eva.Q Lv9
2022-07-11 16:27:02

一举一动，都是承诺，会被另一个人看在眼里，记在心上的。

强连通分量

对于无向图，连通分量很好定义：有边相连的两个点属于一个连通分量。

但对于有向图，需要考虑 “方向”，这一属性，定义：在有向图中，如果存在一条从 到 的路径，也存在一条从 到 的路径，则 和 在同给一个强连通分量里。

这就给解决有向图相关问题提供了两个层面，宏观上，把每一个强连通分量缩成一个点后，图会是一个 DAG ；微观上，每一个强连通分量里的点，任意两个点都可以互达。

kosaraju

求强连通分量。

洛谷P3387

给一个 个点， 条边的有向图，每个点有一个权值，求一条路径，最大化经过的点权值之和（允许多次经过一条边或一个点，但是，重复经过的点，权值只计算一次。）

思路：求强连通分量对应的 DAG 。对于每一个强连通分量，走到里面任何一个点，则整个强连通分量里的点都可以到达，所以缩点以后，每一个强连通分量的权值就是包含的所有的点的权值之和。在缩点以后的图上，跑DP。DP数组 f[u] 表示，走到 这个点的最大权值之和是多少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#define N 10007

bool vis[N];
queue<int> Q;
int a[N], bl[N], w[N], scc, deg[N], f[N];
vector<int> e[N], re[N], post, g[N];

void dfs1(int u) {
    vis[u] = 1;
    for (auto v : re[u])
        if (!vis[v]) dfs1(v);
    post.push_back(u);
}

void dfs2(int u) {
    bl[u] = scc;
    w[scc] += a[u];
    for (auto v : e[u])
        if (!bl[v]) dfs2(v);
}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd();
        e[u].push_back(v);
        re[v].push_back(u);
    }
    for (int u = 1; u <= n; ++u)
        if (!vis[u]) dfs1(u);
    reverse(post.begin(), post.end());
    for (auto u : post)
        if (!bl[u]) {++scc; dfs2(u);}
    for (int u = 1; u <= n; ++u)
        for (auto v : e[u])
            if (bl[u] != bl[v]) {g[bl[u]].push_back(bl[v]); ++deg[bl[v]];}
    for (int u = 1; u <= scc; ++u)
        if (!deg[u]) {f[u] = w[u]; Q.push(u);}
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (auto v : g[u]) {
            f[v] = max(f[v], f[u] + w[v]);
            --deg[v];
            if (!deg[v]) Q.push(v);
        }
    }
    int ans = 0;
    for (int u = 1; u <= scc; ++u) ans = max(ans, f[u]);
    printf("%d\n", ans);
    return 0;
}

2-SAT

2-SAT 问题可以用强连通分量和拓扑排序解决。

2-SAT 问题是一个数字逻辑问题：有 个布尔变量，其中一些布尔变量之间有限制关系；用这 个布尔变量组成序列，使得其满足所有限制关系；判断序列是否存在。

基本的模型是：对于每一个变量建立两个点，一个表示该变量取值为 ， 一个表示该变量取值为 。如果条件是 “ 若 则 ”，就在图中连一条从 指向 的边，同时，对于其逆否命题 “ 若 则 ” ，在图中连一条从 指向 的边。

建立好图之后，在图中跑 kosaraju 算法，求强连通分量。首先每一个强连通分量里的点赋值应该相同，所以如果有一个变量对应的两个点在同一个强连通分量里，则无解。如果想要求一组解，需要找出原图的反拓扑序，所以在使用 kosaraju 算法时，应在原图中计算 post_number ，再在反图上跑 dfs2 ，求出来的每个连通块的标号就是反拓扑序。再遍历每个变量，如果代表该变量取值为 的点拓扑序小于代表该变量取值为 的点，则该变量取值为 。

洛谷P4782

有 个布尔变量，其中一些布尔变量之间有限制关系；用这 个布尔变量组成序列，使得其满足所有限制关系；判断序列是否存在。限制条件形式如下：a val1 b val2 ，含义为 a = val1 || b = val2 ，所以当 a != val1 时，b = val2 ；当 b != val2 时，a = val1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#define N 2000007

bool vis[N];
int bl[N], scc;
vector<int> e[N], re[N], post;

void dfs1(int u) {
    vis[u] = 1;
    for (auto v : e[u])
        if (!vis[v]) dfs1(v);
    post.push_back(u);
}

void dfs2(int u) {
    bl[u] = scc;
    for (auto v : re[u])
        if (!bl[v]) dfs2(v);
}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), a = rd();
        int v = rd(), b = rd();
        e[u + a * n].push_back(v + (1 - b) * n);
        e[v + b * n].push_back(u + (1 - a) * n);
        re[v + (1 - b) * n].push_back(u + a * n);
        re[u + (1 - a) * n].push_back(v + b * n);
    }
    for (int u = 1; u <= (n << 1); ++u)
        if (!vis[u]) dfs1(u);
    reverse(post.begin(), post.end());
    for (auto u : post)
        if (!bl[u]) {++scc; dfs2(u);}
    for (int u = 1; u <= n; ++u)
        if (bl[u] == bl[u + n]) {puts("IMPOSSIBLE"); return 0;}
    puts("POSSIBLE");
    for (int u = 1; u <= n; ++u) {
        if (bl[u] < bl[n + u]) printf("0 ");
        else printf("1 ");
    }
    return 0;
}

洛谷P5782

每个党派有两个人 （ 和 ），两个人里选一个出席委员会。在所有人中，存在限制条件。条件形式如下 a b 表示 a 和 b 不能同时出席。问是否有解，如果有，给出一种委员会的成员表。

思路：挺裸的吧…… 需要注意隐藏条件，就是每个党派的两个人里必须要选恰好一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#define N 320007

bool vis[N];
int bl[N], scc, deg[N];
vector<int> e[N], re[N], post;

void dfs1(int u) {
    vis[u] = 1;
    for (auto v : e[u])
        if (!vis[v]) dfs1(v);
    post.push_back(u);
}

void dfs2(int u) {
    bl[u] = scc;
    for (auto v : re[u])
        if (!bl[v]) dfs2(v);
}

int main() {
    int n = (rd() << 1), m = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd();
        e[u].push_back(v + n); e[v].push_back(u + n); 
        re[v + n].push_back(u); re[u + n].push_back(v);
    }
    for (int i = 1; i <= n; ++i) {
        e[2 * i - 1].push_back(2 * i + n); e[2 * i].push_back(2 * i - 1 + n);
        e[2 * i + n].push_back(2 * i - 1); e[2 * i - 1 + n].push_back(2 * i);
        re[2 * i - 1].push_back(2 * i + n); re[2 * i].push_back(2 * i - 1 + n);
        re[2 * i + n].push_back(2 * i - 1); re[2 * i - 1 + n].push_back(2 * i);
    }
    for (int u = 1; u <= (n << 1); ++u)
        if (!vis[u]) dfs1(u);
    reverse(post.begin(), post.end());
    for (auto u : post)
        if (!bl[u]) {++scc; dfs2(u);}
    for (int u = 1; u <= n; ++u)
        if (bl[u] == bl[u + n]) {puts("NIE"); return 0;}
    for (int u = 1; u <= n; ++u)
        if (bl[u] > bl[n + u]) printf("%d\n", u);
    return 0;
}

洛谷P4171

有 个布尔变量，限制关系形式如下：a = 1 || b = 1 ，问是否有解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#define N 320007

bool vis[N];
int bl[N], scc;
vector<int> e[N], re[N], post;

void dfs1(int u) {
    vis[u] = 1;
    for (auto v : e[u])
        if (!vis[v]) dfs1(v);
    post.push_back(u);
}

void dfs2(int u) {
    bl[u] = scc;
    for (auto v : re[u])
        if (!bl[v]) dfs2(v);
}

inline void work() {
    memset(vis, 0, sizeof(vis));
    memset(bl, 0, sizeof(bl));
    scc = 0; post.clear();
    int n = rd(), m = rd();
    for (int i = 1; i <= (n << 1); ++i) {e[i].clear(); re[i].clear();}
    for (int i = 1; i <= m; ++i) {
        char c1 = getchar();
        for (; c1 != 'm' && c1 != 'h'; c1 = getchar());
        int u = rd();
        char c2 = getchar();
        for (; c2 != 'm' && c2 != 'h'; c2 = getchar());
        int v = rd();
        int a = (c1 == 'm'), b = (c2 == 'm');
        e[u + a * n].push_back(v + (1 - b) * n);
        e[v + b * n].push_back(u + (1 - a) * n);
        re[v + (1 - b) * n].push_back(u + a * n);
        re[u + (1 - a) * n].push_back(v + b * n);
    }
    for (int u = 1; u <= (n << 1); ++u)
        if (!vis[u]) dfs1(u);
    reverse(post.begin(), post.end());
    for (auto u : post)
        if (!bl[u]) {++scc; dfs2(u);}
    for (int u = 1; u <= n; ++u)
        if (bl[u] == bl[u + n]) {puts("BAD"); return;}
    puts("GOOD");
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

acwing370

有 个布尔变量，限制关系以三个位运算的形式给出，AND OR XOR ，问是否有解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#define N 20007

bool vis[N], ans[N];
int bl[N], scc;
vector<int> e[N], re[N], post;

void dfs1(int u) {
    vis[u] = 1;
    for (auto v : e[u])
        if (!vis[v]) dfs1(v);
    post.push_back(u);
}

void dfs2(int u) {
    bl[u] = scc;
    for (auto v : re[u])
        if (!bl[v]) dfs2(v);
}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd(), c = rd();
        string s; cin >> s;
        if (s == "AND") {
            if (c) {
                e[u + n].push_back(u); e[v + n].push_back(v);
                re[u].push_back(u + n); re[v].push_back(v + n);
            } else {
                e[u].push_back(v + n); e[v].push_back(u + n);
                re[v + n].push_back(u); re[u + n].push_back(v);
            }
        } else if (s == "OR") {
            if (c) {
                e[u + n].push_back(v); e[v + n].push_back(u);
                re[v].push_back(u + n); re[u].push_back(v + n);
            } else {
                e[u].push_back(u + n); e[v].push_back(v + n);
                re[u + n].push_back(u); re[v + n].push_back(v);
            }
        } else if (s == "XOR") {
            if (c) {
                e[u].push_back(v + n); e[v].push_back(u + n);
                e[u + n].push_back(v); e[v + n].push_back(u);
                re[v + n].push_back(u); re[u + n].push_back(v);
                re[v].push_back(u + n); re[u].push_back(v + n);
            } else {
                e[u].push_back(v); e[v].push_back(u);
                e[u + n].push_back(v + n); e[v + n].push_back(u + n);
                re[u].push_back(v); re[v].push_back(u);
                re[u + n].push_back(v + n); re[v + n].push_back(u + n);
            }
        }
    }
    for (int u = 1; u <= (n << 1); ++u)
        if (!vis[u]) dfs1(u);
    reverse(post.begin(), post.end());
    for (auto u : post)
        if (!bl[u]) {++scc; dfs2(u);}
    for (int u = 1; u <= n; ++u)
        if (bl[u] == bl[u + n]) {puts("NO"); return 0;}
    puts("YES");
    return 0;
}

acwing371

思路：每场婚礼建两个点，表示是在婚礼开始时举行仪式，还是结束时。枚举每两场婚礼，判断是否有冲突，建图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#define N 20007

bool vis[N];
int bl[N], scc, t[N], s[N], l[N];
vector<int> e[N], re[N], post;

void dfs1(int u) {
    vis[u] = 1;
    for (auto v : e[u])
        if (!vis[v]) dfs1(v);
    post.push_back(u);
}

void dfs2(int u) {
    bl[u] = scc;
    for (auto v : re[u])
        if (!bl[v]) dfs2(v);
}

inline int gettime() {
    int h = rd(), m = rd();
    return h * 60 + m;
}

inline bool tt(int x, int y) {
    if (t[y] >= t[x] + l[x]) return 0;
    if (t[x] >= t[y] + l[y]) return 0;
    return 1;
}

inline bool tw(int x, int y) {
    if (t[x] >= s[y]) return 0;
    if (s[y] - l[y] >= t[x] + l[x]) return 0;
    return 1;
}

inline bool ww(int x, int y) {
    if (s[x] - l[x] >= s[y]) return 0;
    if (s[y] - l[y] >= s[x]) return 0;
    return 1;
}

inline void printpre(int x) {
    int h = t[x] / 60, m = t[x] % 60;
    int h_ = (t[x] + l[x]) / 60, m_ = (t[x] + l[x]) % 60;
    printf("%02d:%02d %02d:%02d\n", h, m, h_, m_);
}

inline void printlst(int x) {
    int h = (s[x] - l[x]) / 60, m = (s[x] - l[x]) % 60;
    int h_ = s[x] / 60, m_ = s[x] % 60;
    printf("%02d:%02d %02d:%02d\n", h, m, h_, m_);
}

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {t[i] = gettime(); s[i] = gettime(); l[i] = rd();}
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            if (tt(i, j)) {
                e[i].push_back(j + n); e[j].push_back(i + n);
                re[i + n].push_back(j); re[j + n].push_back(i);
            }
            if (tw(i, j)) {
                e[i].push_back(j); e[j + n].push_back(i + n);
                re[j].push_back(i); re[i + n].push_back(j + n);
            }
            if (tw(j, i)) {
                e[j].push_back(i); e[i + n].push_back(j + n);
                re[i].push_back(j); re[j + n].push_back(i + n);
            }
            if (ww(i, j)) {
                e[i + n].push_back(j); e[j + n].push_back(i);
                re[i].push_back(j + n); re[j].push_back(i + n);
            }
        }
    }
    for (int u = 1; u <= (n << 1); ++u)
        if (!vis[u]) dfs1(u);
    reverse(post.begin(), post.end());
    for (auto u : post)
        if (!bl[u]) {++scc; dfs2(u);}
    for (int u = 1; u <= n; ++u)
        if (bl[u] == bl[u + n]) {puts("NO"); return 0;}
    puts("YES");
    for (int u = 1; u <= n; ++u)
        if (bl[u] > bl[u + n]) printpre(u);
        else printlst(u);
    return 0;
}
  • Post title：强连通分量 2-SAT
  • Post author：Eva.Q
  • Create time：2022-07-11 16:27:02
  • Post link：https://qyy/2022/07/11/Algorithm/2-SAT/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.