*7-1入度与出度 *

选定数据结构后分别用两个数组记录出度和入度即可。

7-2 图的存储—邻接表

根据题意读入数据建立邻接表，按要求输出即可。

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
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

vector <int> gr[20];
int main() {
	int n, m, s;
	cin >> n >> m >> s;
	for(int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		gr[u].push_back(v);
		if(!s) gr[v].push_back(u);
	}
	for(int i = 1; i <= n; ++i) {
		cout << i-1 << ":";
		for(int j = gr[i].size()-1; j >= 0; --j) {
			cout << gr[i][j]-1 << " ";
		}
		cout << endl;
	}
	return 0;
}

*7-3 满树的遍历 *

首先，确定树是否为 k 阶满树需要检查所有非叶子结点的度是否为 k（通过一个数组记录）。对于给定树，遍历所有结点，记录每个结点的度。若有非叶子结点的度不为 k，则该树不是 k 阶满树。然后，进行前序遍历，从根结点开始，递归访问每个结点及其子结点，记录遍历序列并输出。

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
#include <iostream>
#include <cstring>
#include <vector>

#define N 100010

using namespace std;

int rt;
vector <int> gr[N];
void dfs(int x) {
	if(x != rt) cout << " ";
	cout << x;
	for(int i = 0; i < gr[x].size(); ++i) {
		dfs(gr[x][i]);
	}
}

int cd[N];
int main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		int fa;
		cin >> fa;
		cd[fa]++;
		gr[fa].push_back(i);
		if(!fa) rt = i;
	}
	int key = 0, Max = 0;
	for(int i = 1; i <= n; ++i) {
		if(!cd[i]) continue;
		if(!Max) {
			Max = cd[i];
		}
		else if(Max != cd[i]) {
			key = 1;
			Max = max(Max, cd[i]);
		}
	}
	if(key) cout << Max << " no" << endl;
	else cout << Max << " yes" << endl; 
	dfs(rt);
	return 0;
}

7-4 有向图的拓扑序列

建图的同时记录每个节点的入度和出度，随后按照拓扑序输出即可。

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
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 10;
const int MAXM = 50;

struct Edge {
    int to, next;
};

Edge edges[MAXM * 2]; 
int head[MAXN + 1], cnt = 1; 
int indegree[MAXN + 1]; 
int st[MAXN + 1]; 
int top = -1;

void add_edge(int from, int to) {
    edges[cnt].to = to;
    edges[cnt].next = head[from];
    head[from] = cnt++;
    indegree[to]++;
}

void topological_sort() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        head[i] = 0;
        indegree[i] = 0;
    }
    cnt = 1; 
    top = -1;

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }

    for (int i = 1; i <= n; ++i) {
        if (indegree[i] == 0) {
            st[++top] = i;
        }
    }

    bool has_cycle = false;
    int num_processed = 0;

    while (top != -1) {
        int cur = st[top--];
        cout << cur << " ";
        num_processed++;

        for (int e = head[cur]; e; e = edges[e].next) {
            int next = edges[e].to;
            if (--indegree[next] == 0) {
                st[++top] = next;
            }
        }
    }

    if (num_processed < n) {
        cout << "\n0";
        has_cycle = true;
    } else {
        cout << "\n";
    }
}

int main() {
    topological_sort();
    return 0;
}

7-5【模板】Floyd

模板

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
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 110

using namespace std;

int dis[N][N];
int main() {
	int n, m;
	cin >> n >> m;
	memset(dis, 0x3f, sizeof(dis));
	for(int i = 1; i <= n; ++i) dis[i][i] = 0;
	for(int i = 1; i <= m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		dis[u][v] = dis[v][u] = min(dis[v][u], w);
	}
	for(int k = 1; k <= n; ++k) {
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= n; ++j) {
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
            if(j != 1) cout << " ";
			cout << dis[i][j];
		}
		cout << endl;
	}
	return 0;
}

7-6 Dijkstra算法（模板）

模板

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long
#define N 2525
#define M 6262

using namespace std;

ll head[N], ver[M<<1], nxt[M<<1], dis[M<<1];
int tot;
void add(ll s, ll t, ll w) {
	ver[++tot] = t;
	nxt[tot] = head[s];
	dis[tot] = w;
	head[s] = tot;
}

struct node {
	ll x, dis;
	bool operator < (const node &a) const {
		return dis > a.dis;
	}
};

priority_queue <node> q;
int v[N];
ll ans[N];

int main() {
	int n, m, s, t;
	cin >> n >> m >> s >> t;
	for(int i = 1; i <= m; ++i) {
		ll si, ti, wi;
		cin >> si >> ti >> wi;
		add(si, ti, wi);
		add(ti, si, wi);
	}
	q.push((node) {s, 0});
	memset(ans, 0x3f, sizeof(ans));
	ans[s] = 0;
	while(q.size()) {
		node nw = q.top();
		q.pop();
		if(v[nw.x]) continue;
		v[nw.x] = 1;
		for(int i = head[nw.x]; i; i = nxt[i]) {
			if(v[ver[i]]) continue;
			if(ans[nw.x] + dis[i] < ans[ver[i]]) {
				ans[ver[i]] = ans[nw.x] + dis[i];
				q.push((node) {ver[i], ans[ver[i]]});
			}
		}
	}
	cout << ans[t];
	return 0;
}

7-7 最小生成树

模板

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define N 1000010

using namespace std;

struct node {
	int x, y, z;
	bool operator < (const node &a) const{
		return z < a.z;
	}
}st[N];
int fa[N];

int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) fa[i] = i;
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &st[i].x, &st[i].y, &st[i].z);
	}
	int ans = 0;
	sort(st + 1, st + m + 1);
	for(int i = 1; i <= m; ++i) {
		if(n == 1) break;
		if(find(st[i].x) != find(st[i].y)) {
			fa[find(st[i].x)] = find(st[i].y);
			ans += st[i].z;
			n--;
		}
	}
	printf("%d", ans);
	return 0;
}

7-8 最小生成树构造-prim算法

朴素解法是通过prim算法求出每次要建立的边存起来，按题意排序后输出即可，也可以参照下面的代码。

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
#include <iostream>
#include <vector>
#include <queue>


using namespace std;

struct Edge {
    int from, to, cost;
};

bool operator<(const Edge& e1, const Edge& e2) {
    return e1.cost > e2.cost;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<Edge> > graph(n + 1); 
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back((Edge){u, v, w});
        graph[v].push_back((Edge){v, u, w}); 
    }

    vector<bool> visited(n + 1, false);
    priority_queue<Edge> pq;
    pq.push((Edge){0, 1, 0}); 

    while (!pq.empty()) {
        Edge e = pq.top();
        pq.pop();

        if (visited[e.to]) continue;
        visited[e.to] = true;

        if (e.from != 0) {
            cout << min(e.from, e.to) << "," << max(e.from, e.to) << "," << e.cost << endl;
        }

        for (int j = 0; j < graph[e.to].size(); ++j) {
            Edge next = graph[e.to][j];
            if (!visited[next.to]) {
                pq.push(next);
            }
        }
    }


    return 0;
}

7-9 浪漫侧影

首先通过后序遍历和中序遍历建立二叉树，对于左视图遍历二叉树的每一层输出从左向右方向上的第一个不为空的结点，对于右视图也同理（可以通过层序遍历实现）。

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
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int head[30], ver[30], nxt[30];
int tot = 0;
void add(int x, int y) {
	ver[++tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
}

int A[30], B[30];
int cnt, md;
int build(int d, int l, int r) {
	int x = B[cnt--];
	add(d, x);
	if(md < d) md = d;
	if(l == r) return A[l];
	int pos = -1;
	for(int i = l; i <= r; ++i) {
		if(x == A[i]) {
			pos = i;
			break;
		}
	}
	if(pos + 1 <= r) build(d + 1, pos + 1, r);
	if(l <= pos - 1) build(d + 1, l, pos - 1);
	return A[pos];
}

int main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> A[i];
	}
	for(int i = 1; i <= n; ++i) {
		cin >> B[i];
	}
	cnt = n;
	build(1, 1, n);
	cout << "R:";
	for(int i = 1; i <= md; ++i) {
		int j = head[i];
		while(nxt[j]) j = nxt[j];
		cout << " " << ver[j];
	}
	cout << endl;
	cout << "L:";
	for(int i = 1; i <= md; ++i) {
		cout << " " << ver[head[i]];
	}
	return 0;
}

7-10 最短路计数

设边权为1，跑Dijkstra算法，在更新最小花费的同时用ans数组记录最短路数量。如果花费相等就继承前驱节点的最短路数量，否则相加。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define N 100010
#define M 200020
#define mod 100003

using namespace std;

int tot;
int head[N], ver[M<<1], nxt[M<<1];

void add(int x, int y) {
	ver[++tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
} 

queue <int> q;
int v[N], ans[N], dis[N];

int main() {
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i) {
		int fir, sec;
		cin >> fir >> sec;
		add(fir, sec);
		add(sec, fir);
	}
	ans[1] = 1;
	q.push(1);
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	v[1] = 1;
	while(q.size()) {
		int nw = q.front();
		q.pop();
		for(int i = head[nw]; i; i = nxt[i]) {
			int y = ver[i];
			if(dis[nw] + 1 <= dis[y]) {
				dis[y] = dis[nw] + 1;
				ans[y] = (ans[y] + ans[nw]) % mod;
				if(!v[y]) {
					q.push(y);
					v[y] = 1;
				}
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		cout << ans[i] << endl;
	}
	return 0;
}