这一部分将带来Course2 week1的习题解析。

选择题

选择题1

给定有向图的邻接列表表示，其中每个顶点记录其出去的边的数组（不是入边的数组），在最坏的情况下，需要多长时间来计算给定顶点的入度？

像往常一样，我们使用$n$和$m$分别表示给定图的顶点和边的数量。还有，让$k$表示顶点的最大入度。（回想一下顶点的入度是输入它的边数。）

  • 无法确定
  • $\theta(k)$
  • $\theta(m)$
  • $\theta(n)$

只要遍历一遍全部的边，就可以计算出每个顶点的入度，所以为$\theta(m)$

选择题2

考虑以下问题：给定有$n$个顶点$m$条边的无向图$G$以及两个顶点$s$和$t$，是否存在至少一个$s-t$路径？

如果$G$用邻接列表表示，则可以在$\theta(m+n)$时间解决上述问题 ，使用BFS或DFS。

如果$G$用邻接矩阵表示。在最坏的情况下，需要什么运行时间才能解决上述计算问题？（假使，假设$G$没有平行的边缘。）

  • $\theta(n^2)$
  • $\theta(m+n\log n )$
  • $\theta(m+n)$
  • $\theta(m\times n)$

可以先通过邻接矩阵构造邻接表，时间为$\theta(n^2)$，接着使用BFS，时间复杂度为$\theta(n+m)$，因为$m= O(n^2)$，所以总共的时间复杂度为$\theta(n^2)$

选择题3

此问题探讨了关于图距离的两个定义之间的关系。在这个问题中，我们只考虑无向和连接的图。图的直径是任意两点$s,t$的最短距离的最大值。（回想一下$s,t$之间的最短路径距离是$s,t$中边数最少的路径。）

接下来，对于顶点$s$，令$l(s)$表示所有顶点$t$距离$s$的最短距离的最大值。图的半径是所有$l(s)$中的最小值。

对于半径$r$和直径$d$，以下哪个不等式总是成立

  • $r\ge d$
  • $r\le d / 2$
  • $r\ge d / 2$
  • $r\le d$

令$c$是使得$l(s)$最小的顶点，$d(x,y)$表示$x,y$之间的最短距离。

那么对于任意的顶点$s,t$，显然$d(s,c) \le l(c) =r,d(t,c) \le l(c) =r$，路径$s-c-t$的长度显然大于等于$s-t$的最短路径，由$s,t$的任意性可知

另外，由定义可知$l(s) \le d$，所以$r\le d$，因此第三项和第四项正确。

选择题4

考虑我们用于计算基于深度优先搜索的拓扑排序的算法（即，不是“直接解决方案”）。假设图$G$不是非循环的。显然它不会计算拓扑顺序（因为不存在）。它是否计算了一个最小化后退边数的排序？

例如，考虑具有六个有向边的四节点图$(s,v),(s,w),(v,w),(v,t),(w,t),(t,s)$ 。假设顶点的顺序是$s,v,w,t$。然后有一个向后的弧线，$(t,s)$弧。没有顺序的顶点具有零向后弧。

  • 总是
  • 当且仅当图示有向图
  • 有时候可以，有时候不行
  • 从不

这题没有完全理解，感觉是第三个选项。

选择题5

向有向图添加一个额外边$G$，强连接组件(SCC)的数量.？

  • 永远不会减少超过1
  • 永远不会减少
  • 肯定不会改变
  • 可以保持不变

查看下图即可，添加一个额外边，SCC数量不变，最后一项正确：

编程题

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;

const int N = 1e6;

//定义图
vector <int> G[N], Grev[N];
//判断是否访问过
int flag[N];
//leader数组
int leader[N];
//结束时间
int finish[N];
//结束时间->节点编号
int Index[N];
//leader
int s;
//访问时间
int t;
//节点数量
int n = 1;

bool cmp(int a, int b){
    return a > b;
}

//深度优先搜索（第一轮）
void DFS_v1(vector <int> Graph[], int i){
    //初始化栈
    stack <int> Q;
    Q.push(i);
    flag[i] = 1;
    //记录顺序
    vector <int> tmp;
    while (!Q.empty()){
        int u = Q.top();
        Q.pop();
        leader[u] = s;
        //存储结果
        tmp.push_back(u);
        //入队
        for (int k = 0; k < Graph[u].size(); k++){
            int v = Graph[u][k];
            if (flag[v] == 0){
                flag[v] = 1;
                Q.push(v);
            }
        }
    }
    //计算finish, Index;
    for (int j = tmp.size() - 1; j >= 0; j--){
        int u = tmp[j];
        t++;
        finish[u] = t;
        Index[t] = u;
    }
}

//深度优先搜索（第二轮）
void DFS_v2(vector <int> Graph[], int i, int& cnt){
    //初始化栈
    stack <int> Q;
    Q.push(i);
    flag[i] = 1;
    while (!Q.empty()){
        int u = Q.top();
        Q.pop();
        //入队
        for (int k = 0; k < Graph[u].size(); k++){
            int v = Graph[u][k];
            if (flag[v] == 0){
                flag[v] = 1;
                Q.push(v);
            }
        }
        //更新计数
        cnt++;
    }
}

//递归版本
//void DFS_v1(vector <int> Graph[], int i){
//    flag[i] = 1;
//    leader[i] = s;
//    for (int k = 0; k < Graph[i].size(); k++){
//        int j = Graph[i][k];
//        if (flag[j] == 0){
//            DFS_v1(Graph, j);
//        }
//    }
//    t++;
//    finish[i] = t;
//    //记录时间和索引的关系
//    Index[t] = i;
//}

//void DFS_v2(vector <int> Graph[], int i, int &cnt){
//    flag[i] = 1;
//    cnt++;
//    for (int k = 0; k < Graph[i].size(); k++){
//        int j = Graph[i][k];
//        if (flag[j] == 0){
//            DFS_v2(Graph, j, cnt);
//        }
//    }
//}

int main(){
    //输入
    //文件名
    char filename[] = "SCC.txt";
    freopen(filename, "r", stdin);
    //记录节点数量
    int u, v;
    while (scanf("%d %d", &u, &v) != EOF){
        n = max(n, u);
        n = max(n, v);
        G[u].push_back(v);
        Grev[v].push_back(u);
    }

    //第一轮
    //初始化
    memset(flag, 0, sizeof(flag));
    t = 0;
    for (int i = n; i >= 1; i--){
        if (flag[i] == 0){
            //设置leader
            s = i;
            DFS_v1(Grev, i);
        }
    }

    //第二轮
    memset(flag, 0, sizeof(flag));
    //记录SCC的元素数量
    vector <int> res;
    for (int k = n; k >= 1; k--){
        int i = Index[k];
        int cnt = 0;
        if (flag[i] == 0){
            DFS_v2(G, i, cnt);
            res.push_back(cnt);
        }
    }

    //排序
    sort(res.begin(), res.end(), cmp);
    //输出
    int m = (res.size() > 5)? 5: res.size();
    for (int i = 0; i < m; i++){
        printf("%d", res[i]);
        if (i < m - 1){
            printf(", ");
        }else{
            printf("\n");
        }
    }

    return 0;
}

思考题

思考题1

In the 2SAT problem, you are given a set of clauses, where each clause is the disjunction of two literals (a literal is a Boolean variable or the negation of a Boolean variable). You are looking for a way to assign a value “true” or “false” to each of the variables so that all clauses are satisfied —- that is, there is at least one true literal in each clause. For this problem, design an algorithm that determines whether or not a given 2SAT instance has a satisfying assignment. (Your algorithm does not need to exhibit a satisfying assignment, just decide whether or not one exists.) Your algorithm should run in $O(m+n)$ time, where $m$ and $n$ are the number of clauses and variables, respectively. [Hint: strongly connected components.]

参考资料：https://wenku.baidu.com/view/0f96c3daa58da0116c1749bc.html

假设布尔变量集为$B=\left\{b_{1}, b_{2}, \cdots, b_{n}\right\}$，包含$B$元素取反的集合为$\hat{B}=\left\{b_{1}, b_{2}, \cdots, b_{n}, \neg b_{1}, \neg b_{2}, \cdots, \neg b_{n}\right\}$，将$\hat B$中$2n$个节点视为图的节点，我们的目标是选择这$2n$个节点中$n$个节点（$b_i ,\neg b_i$不能同时出现），使得这些节点的值为true。接着考虑$x\vee y $表示的含义，注意到我们有

所以如果选择了$\neg x$，即$\neg x = \text{true}$，那么必然要选择$y$（即$\neg y = \text{false}$）；反之，如果选择了$\neg y$，那么必然要选择$x$，所以$x\vee y$，对应了图中两条边$(\neg x, y),(\neg y, x)$。注意到如果选择了$y$，那么不一定需要选择$\neg x$，所以该边是有向的。因为一共有$m$组clause，所以图中一共有$2m$条边，这样就构造了一个有向图。

接着对该图计算SCC，如果存在$b_i , \neg b_i$属于同一个强连通分量，那么该2SAT问题必然无解，反之有解，因为该图一共有$2n$个节点，$2m$条边，所以时间复杂度为$O(m+n )$