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

这次回顾Course2 week1的算法。

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

BFS

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
#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

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
#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

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#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;
}