斯坦福 算法1 第四周作业

来自斯坦福网站的Algorithms: Design and Analysis，与目前coursera上的版本内容没有变化，不过时间安排略有不同。

1. Problem Set 4

从出度邻接表计算每个点的入度，必须遍历所有的边。

使用邻接矩阵，计算s到t是否联通。先要把邻接矩阵改为邻接表，这就是平方复杂度。然后再用DFS或者BFS。

这题的答案解释很有必要认真看。有时候把问题思路形式化写出来真的不容易。

可以找到反例，所以有时可以有时不行。

上面三个都有反例，其中第一个可以想一个只差一条边就变成强联通图的SCC构成的图，加一条边之后SCC数量变成了1。

2. Optional Theory Problems

2SAT问题。看这个英文描述我是真没看懂是啥，虽然SAT问题很有名，不过很久不看突然看到确实很懵。大致就是有n个布尔变量，每两个布尔变量之间满足一些限制，比如a为真或b为假这种算是一个限制，一共有m个限制条件。需要找到给定的m个限制条件下是否存在可行的n个布尔变量的取值能够满足条件。

这里显然考虑用图搜索算法了，提示也说了用找强联通图的方法。于是把问题建模为一个判断一个图是否是强联通分量的问题。

建图需要考虑点与边分别是啥。点很明显得考虑变量，而边就是每个条件了。假如每个点的取值都满足边代表的限制条件，那么就说明每个点都能与周围的点相连，而且边还应该是无向的（或是双向的）。也就是说这时候的整个图应该是强联通的。

那么问题来了，如果使用简单的每个变量作为点，每个点的取值不确定。我们需要去确定是否存在n个点的某种赋值让整个图是个强联通图，所以整个算法的复杂度会变成$O(2^{n})$O(2n)，而且边也很不好确定是否联通，每次还需要尝试对应的点取值是否满足边表示的限制条件决定是否联通，因此这么做不行。

但是思路应该是对的，沿着这个思路继续走。需要把每个变量拆开成两个，分别代表真和假两种取值，每两个变量有四个点，它们之间如果有限制条件，那么限制条件对应的边也能够确定。比如 a为真或b为假这个条件，四个点a,-a,b,-b分别代表a和b取真或假。那么a与b和-b都有边相连，-b与-a也有边相连。如果这个图是联通图就代表存在满足条件的n个赋值。而整个算法使用DFS也只需要$O(2n+4m)$O(2n+4m)的复杂度，也满足条件。

3. Programming Assignment 4

这题就是课上讲的找SCCs算法的实现，只不过数据比较多。但是warning说的问题我似乎没遇上，但是却遇上了别的神奇的bug，不过可能也就是因为数据太多导致的。

首先需要考虑图的表示。显然要用邻接表，因为使用C++实现，所以可以考虑二维vector或者map，这里用了unordered_map<int,vector>表示。同时因为还需要图的逆向表示，因此直接在读取数据的时候存成两个就行。算了一下占用内存还可以接受：

int readGraph(string fileName,unordered_map<int,vector<int>>& G, unordered_map<int,vector<int>>& Grev) {
    cout << "read data from "<< fileName <<endl;
    ifstream input(fileName);
    string line;
    int res = 0;
    int u,v;
    if(input) {
        while(getline(input,line)) {
            istringstream ist(line);
            ist >> u;
            ist >> v;
            G[u].push_back(v);
            Grev[v].push_back(u);
            res = max(res,max(u,v));
        }
    }
    for(int i = 1; i <= res; i++){
        if(G.find(i) == G.end()){
            G[i].push_back(0);
            G[i].pop_back();
        }
        if(Grev.find(i) == Grev.end()){
            Grev[i].push_back(0);
            Grev[i].pop_back();
        }
    }
    return res;
}

然后就是两次DFS-Loop。算法的伪代码里将两次DFS-Loop写为同一个算法，这里也这么实现了，不过可能有些地方两次循环做的还是稍微有些不一样。

先看DFS的代码：

int DFS(unordered_map<int,vector<int>>& G, int u, int& s, vector<bool>& visited,vector<int>& scores) {
    int res = s;
    int next;
    for(int i = 0; i < G[u].size(); i++) { //此处如果用for(int next : G[u])有个神奇的bug
        next = G[u][i];
        if(!visited[next]) {
            visited[next] = true;
            DFS(G,next,s,visited,scores);
        }
    }
    scores[s] = u;
    s++;
    res = s-res;
    return res;
}

需要说的部分就是scores这个结构，表示的是对每个结点计算的f值。其中下标表示f值本身，而每个元素值表示结点的序号或者说是取值。这样直接从后往前遍历就能实现按f值降序遍历了。

再看循环体DFS_Loop:

vector<int> DFS_Loop(unordered_map<int,vector<int>>& G, vector<int>& scores, vector<bool>& visited, bool first,vector<int>& numbers) {
    int s = 0, n = scores.size();
    int count;
    int sum = 0;
    vector<int> res(n);
    for(int i = n-1; i >= 0; i--) {
        if(!visited[scores[i]]) {
            visited[scores[i]] = true;
            count = DFS(G,scores[i],s,visited,res);
            if(!first && count > 200) {
                cout <<"count:"<< count << " "<< s<<endl;
                numbers.push_back(count);
            }
            sum += count;
        }
    }
    cout << "sum: "<< sum << endl;
    return res;
} 

其中numbers是记录第二次遍历的时候每个SCC的大小的，第一次遍历时用不到。sum是为了检验是否遍历了所有的点。而输出的结果res，第一遍遍历的时候就是给每个结点打的f值的表示，作为第二次遍历时候的scores输入。第二次遍历时候的结果是不需要的。

main函数没啥特别的：

int main() {
    unordered_map<int,vector<int>> G,Grev;
    int length = readGraph("SCC.txt",G,Grev);

    vector<int> points; //第一次DFS_Loop循环里遍历每个结点的顺序（元素值表示结点值，任意即可，这里是按元素值降序）
    for(int i = 0; i < length; i++)
        points.push_back(length-i);

    vector<bool> visited(length+1);
    vector<int> numbers;
    cout << "First DFS_Loop..."<<endl;
    vector<int> scores = DFS_Loop(Grev,points,visited,true,numbers);//第二次DFS_Loop循环里遍历
    //每个结点的顺序，按第一次遍历得到的分数降序，scores的下标表示分数，下标对应元素表示结点号

    // set<int> test(scores.begin(),scores.end());

    cout << "Second DFS_Loop..."<<endl;
    visited.assign(length+1,false);
    DFS_Loop(G,scores,visited,false,numbers);

    sort(numbers.rbegin(),numbers.rend()); //偷懒直接排序，可以用堆的方式复杂度nlogk取前k大的数
    for(int i = 0; i < 5; i++)
        cout << "results: "<<numbers[i] << " ";

    return 0;
}

如果不考虑numbers计数排序的部分，整个算法应该是线性的。稍微需要理解的就是DFS-Loop的输出。第一次输出的数组作为第二次遍历时候的scores实参。