斯坦福算法专项课程Course2 week1算法实现

这次回顾Course2 week1的算法。

课程地址：https://www.coursera.org/specializations/algorithms

BFS

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

const int N = 1e6;

//定义图
vector <int> G[N];
//节点数量
int n = 1;
//判断是否访问过
int flag[N];
//存储结果
vector <int> res;

void BFS(vector <int> Graph[], int i){
    //初始化栈
    queue <int> Q;
    Q.push(i);
    flag[i] = 1;
    while (!Q.empty()){
        int u = Q.front();
        res.push_back(u);
        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);
            }
        }
    }
}

void Print(vector <int> res){
    int m = res.size();
    for (int i = 0; i < m; i++){
        printf("%d", res[i]);
        if (i < m - 1){
            printf("->");
        }else{
            printf("\n");
        }
    }
}

int main(){
    //文件名
    char filename[] = "test_data.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);
    }

    //初始化
    memset(flag, 0, sizeof(flag));
    for (int i = 1; i <= n; i++){
        if (flag[i] == 0){
            BFS(G, i);
        }
    }
    //输出
    Print(res);

    return 0;
}

DFS

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

const int N = 1e6;

//定义图
vector <int> G[N];
//节点数量
int n = 1;
//判断是否访问过
int flag[N];
//存储结果
vector <int> res;

void DFS(vector <int> Graph[], int i){
    flag[i] = 1;
    res.push_back(i);
    for (int k = 0; k < Graph[i].size(); k++){
        int j = Graph[i][k];
        if (flag[j] == 0){
            DFS(Graph, j);
        }
    }
}

void Print(vector <int> res){
    int m = res.size();
    for (int i = 0; i < m; i++){
        printf("%d", res[i]);
        if (i < m - 1){
            printf("->");
        }else{
            printf("\n");
        }
    }
}

int main(){
    //文件名
    char filename[] = "test_data.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);
    }

    //初始化
    memset(flag, 0, sizeof(flag));
    for (int i = 1; i <= n; i++){
        if (flag[i] == 0){
            DFS(G, i);
        }
    }
    //输出
    Print(res);


    return 0;
}

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){
    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[] = "test_data.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;
}