挑战程序设计竞赛-day13

强连通分量分解

强连通

对于一个有向图顶点的子集S，如果在S内任取两个顶点u和v，都能找到一条从u到v的路径，那么就成S是强连通的。

强连通分量

如果在强连通的顶点集合S中家人其他任意顶点集合后，它都不再是强连通的，那么就称S为原图的一个强连通分量（SCC：Strongly Connected Component）

任意有向图都可以分解为若干不相干的强连通分量，这就是强连通分量分解。把分解后的强连通分量所成一个顶点，就得到了一个DAG（有向无环图）

强连通分量分解（Kosaraju算法）

通过两次DFS实现。

第一次DFS时，选取任意顶点作为起点，遍历所有尚未访问过的顶点，并在回溯前给顶点标号。对剩余的未访问过的顶点，不断重复上述过程。

第二次DFS时，先将所有边反向，然后以标号最大的点为起点进行DFS。这样DFS所遍历的顶点集合就构成了一个强连通分量。之后，只要还有尚未访问的顶点，就从中选取标号最大的顶点不断重复上述过程。

具体过程如下图：

此算法只进行了两次DFS，因而总的复杂度是$O(|V| + |E|)$

#include <bits/stdc++.h>
using namespace std;
const int MAX_V = 10;
int V;  // 顶点数
vector<int> G[MAX_V];    // 图的邻接表示
vector<int> rG[MAX_V];   // 把边反向后的图
vector<int> vs;        // 后续遍历顺序的顶点列表
bool used[MAX_V];        // 访问标记
int cmp[MAX_V];          // 所属强连通分量的拓扑序

void add_edge(int from, int to) {
    G[from].push_back(to);
    rG[to].push_back(from);
}

void dfs(int v) {
    used[v] = true;
    for(int i = 0; i < G[v].size(); i++) {
        if(!used[G[v][i]]) {
            dfs(G[v][i]);
        }
    }
    vs.push_back(v);
}

void rdfs(int v, int k) {
    used[v] = true;
    cmp[v] = k;
    for(int i = 0; i < rG[v].size(); i++) {
        if(!used[rG[v][i]]) {
            rdfs(rG[v][i], k);
        }
    }
}

int scc() {
    memset(used, 0, sizeof(used));
    vs.clear();
    for(int v = 0; v < V; v++) {
        if(!used[v]) {
            dfs(v);
        }
    }
    memset(used, 0, sizeof(used));
    int k = 0;
    for(int i = vs.size() - 1; i >= 0; i--) {
        if(!used[vs[i]]) {
            rdfs(vs[i], k++);
        }
    }
    return k;
}

POJ 2186：Popular Cows

void solve() {
    V = N;
    for(int i = 0; i < M; i++) {
        add_edge(A[i] - 1, B[i] - 1);
    }
    int n = scc();

    // 统计备选解的个数
    int u = 0, num = 0;
    for(int v = 0; v < V; v++) {
        if(cmp[v] == n - 1) {
            u = v;
            num++;
        }
    }

    // 检查是否从所有点可达
    memset(used, 0, sizeof(used));
    rdfs(u, 0); // 重用强连通分量的代码
    for(int v = 0; v < V; v++) {
        if(!used[v]) {
            num = 0;
            break;
        }
    }
    printf("%d\n", num);
}

int main() {
    while(scanf("%d%d", &N, &M) != EOF) {
        for(int i = 0; i < M; i++) {
            scanf("%d%d", &A[i], &B[i]);
        }
        solve();
        for(int i = 0; i < N; i++) {
            G[i].clear();
            rG[i].clear();
        }
    }
    
}

2-SAT

给定一个布尔方程， 判断是否存在一组布尔变量的真值指派使整个方程为真的问题，被称为布尔方程的可满足性问题（SAT）

SAT问题是NP完全的，但对于满足一定限制条件的SAT问题，还是能够有效求解的。我们将下面这种布尔方程称为合取范式。
$(a∨b∨…)∧(c∨d∨…)∧…$
其中a, b, …称为文字，它是一个布尔变量或其否定。像$(a∨b∨...)$这样用$∨$连接的部分称为子句。如果合取范式的每个子句中的文字个数都不超过两个，那么对应的SAT问题又称为2-SAT问题。

利用强连通分量分解，可以在布尔公式子句数的线性时间内解决$2-SAT$问题。首先利用$\rightarrow$(蕴含)将每个句子$(a∨b)$改写成等价形式$¬a⇒b∧¬b⇒a$

这样，原布尔公式就变成了把$a⇒b$形式的布尔公式用$∧$连接起来的形式。对每个布尔变量$x$，构造两个顶点分别代表$x$和$¬x$，以$⇒$关系为边建立有向图。此时，如果图上的$a$点能够到达$b$点的话，就表示当$a$为真时$b$也一定为真。因此，该图中同一个强连通分量中所含的所有文字的布尔值均相同。

如果存在某个布尔变量$x$， $x$和$¬x$均在同一个强连通分量中，则显然无法令整个布尔公式的值为真。反之，如果不存在这样的布尔变量，那么对于每个布尔变量$x$，让

x 所在的强连通分量的拓扑序在¬x 所在的强连通分量之后 ⇔ x 为真

就是使得该公式的值为真的一组合适的布尔变量赋值。

实现

int main() {
    // 布尔表达式为(a)
    // 构造6个顶点，分别对应a, b, c, ~a, ~b, ~c
    V = 6;
    add_edge(3, 4);
    add_edge(1, 0);

    add_edge(4, 2);
    add_edge(5, 1);

    add_edge(2, 3);
    add_edge(0, 5);

    // 进行强连通分量分解
    scc();

    // 判断x和~x是否在不同的强连通分量中
    for(int i = 0; i < 3; i++) {
        if(cmp[i] == cmp[i + 3]) {
            cout << "NO" << endl;
            return 0; 
        }
    }

    cout << "YES" << endl;
    for(int i = 0; i < 3; i++) {
        if(cmp[i] > cmp[3 + i]) {
            cout << "true" << " ";
        } else {
            cout << "false" << " ";
        }
    }
    cout << endl;
    return 0;
}

POJ 3683：Priest John’s Busiest Day

约翰是街区里唯一的神父。假设有N 对新人打算在同一天举行结婚仪式。第i 对新人的结婚仪式的时间为$S_i$ 到$T_i$，在其仪式开始时或是结束时需要进行一个用时$D_i$ 的特别仪式（也就是从$S_i$ 到$S_i+D_i$ 或是从$T_i-D_i$到$T_i$），该特别仪式需要神父在场。请判断是否可以通过合理安排每个特别仪式在开始还是结束时进行，从而保证神父能够出席所有的特别仪式。如果可能的话，请输出出席各个特别仪式的时间。当然，神父不可能同时出席多个特别仪式。不过神父前往仪式的途中所花费的时间可以忽略不计，神父可以在出席完一个特别仪后，立刻出席另一个开始时间与其结束时间相等的特别仪式

思路

对于每个结婚仪式i，只有在开始或结束时进行特别仪式两种选择。因此可以定义变量$x_i$

$x_i 为真 \leftrightarrow 在开始时进行特别仪式$

这样，对于结婚仪式$i$和$j$，如果$[S_i, S_i + D_i]$和$[S_j, S_j + D_j]$冲突，就有$¬xi∨¬xj$为真。对于开始和开始，开始和结束，结束和开始，结束和结束等总共四种情况，能得到类似的条件。要保证所有的特别仪式的时间不冲突，质押考虑将所有的子句用$∧$连接起来所得到的的布尔公式就好了。

这样就可以将原问题转换为2-SAT问题。接下来只要进行强连通分量分解判断是否有使得布尔公式值为真的一组布尔变量赋值就好了。

代码

void solve() {
    // 0 : N-1  -> x_i
    // N : 2N-1 -> ~x_i
    V = 2 * N;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < i; j++) {
            if(min(S[i] + D[i], S[j] + D[j]) > max(S[i], S[j])) {
                // ~x_i or ~x_j
                add_edge(i, N + j);
                add_edge(j, N + i);
            }
            if(min(S[i] + D[i], T[j]) > max(S[i], T[j] - D[j])) {
                // ~x_i or x_j
                add_edge(i, j);
                add_edge(N + j, N + i); 
            }
            if(min(T[i], S[j] + D[j]) > max(T[i] - D[i], S[j])) {
                // x_i or ~x_j
                add_edge(N + i, N + j);
                add_edge(j, i);
            }
            if(min(T[i], T[j]) > max(T[i] - D[i], T[j] - D[j])) {
                // x_i or x_j
                add_edge(N + i, j);
                add_edge(N + j, i);
            }
        }
    }
    scc();

    // 判断是否可满足
    for(int i = 0; i < N; i++) {
        if(cmp[i] == cmp[i + N]) {
            printf("NO\n");
            return ;
        }
    }

    // 如果可满足，给出一组解
    printf("YES\n");
    for(int i = 0; i < N; i++) {
        if(cmp[i] > cmp[N + i]) {
            // 即x_i为真,即在婚礼仪式开始前举行
            printf("%02d:%02d %02d:%02d\n", S[i] / 60, S[i] % 60, (S[i] + D[i]) / 60, (S[i] + D[i]) % 60);
        } else {
            printf("%02d:%02d %02d:%02d\n", (T[i] - D[i]) / 60, (T[i] - D[i]) % 60, T[i] / 60, T[i] % 60);
        }
    }
}

int main() {
    int s1, s2, t1, t2, t;
    while(scanf("%d", &N) != EOF) {
        for(int i = 0; i < N; i++) {
            scanf("%d:%d %d:%d%d", &s1, &s2, &t1, &t2, &t);
            S[i] = s1 * 60 + s2;
            T[i] = t1 * 60 + t2;
            D[i] = t;
            // cout << s1 << " " << s2 << " " << t1 << " " << t2 << " " << t << endl;
        }
        solve();
        for(int i = 0; i < 2 * N; i++) {
            G[i].clear();
            rG[i].clear();
        }
    } 
}