网站标题能改吗,安装 wordpress多人,网络营销专业学什么课程,广西排名前十的模板厂题目一#xff1a;DS图 -- 图的连通分量
题目描述#xff1a;
输入无向图顶点信息和边信息#xff0c;创建图的邻接矩阵存储结构#xff0c;计算图的连通分量个数。
输入要求#xff1a;
测试次数t
每组测试数据格式如下#xff1a;
第一行#xff1a;顶点数 顶点…题目一DS图 -- 图的连通分量
题目描述
输入无向图顶点信息和边信息创建图的邻接矩阵存储结构计算图的连通分量个数。
输入要求
测试次数t
每组测试数据格式如下
第一行顶点数 顶点信息
第二行边数
第三行开始每行一条边信息
输出要求
每组测试数据输出顶点信息和邻接矩阵信息
输出图的连通分量个数具体输出格式见样例。
每组输出直接用空行分隔。
输入样例
3
4 A B C D
2
A B
A C
6 V1 V2 V3 V4 V5 V6
5
V1 V2
V1 V3
V2 V4
V5 V6
V3 V5
8 1 2 3 4 5 6 7 8
5
1 2
1 3
5 6
5 7
4 8
输出样例
A B C D
0 1 1 0
1 0 0 0
1 0 0 0
0 0 0 0
2V1 V2 V3 V4 V5 V6
0 1 1 0 0 0
1 0 0 1 0 0
1 0 0 0 1 0
0 1 0 0 0 0
0 0 1 0 0 1
0 0 0 0 1 0
11 2 3 4 5 6 7 8
0 1 1 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 1 0
0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
3
代码示例
#include iostream
#include string
#include cstring
#include iomanip
#include algorithm
#include cmath
#include queue
using namespace std;class Map {
private:int** array;string* vertex;int n;bool visited[20];int partnumber;
public:Map() {cin n;array new int* [n];for (int i 0; i n; i) {array[i] new int[n];for (int j 0; j n; j) array[i][j] 0;}vertex new string[n];for (int i 0; i n; i) cin vertex[i];partnumber 0;}int findIndex(string str) {for (int i 0; i n; i) if (str vertex[i]) return i;return -1;}void createMap() {int n, v1, v2;string ch1, ch2;cin n;for (int i 0; i n; i) {cin ch1 ch2;v1 findIndex(ch1);v2 findIndex(ch2);array[v1][v2] 1, array[v2][v1] 1;}}void DFSTraverse() {for (int i 0; i n; i) visited[i] false;for (int i 0; i n; i) {if (!visited[i]) {DFS(i);partnumber;}}}void DFS(int v) {visited[v] true;int* temp new int[n];int pos 0;for (int i 0; i n; i) if (array[v][i]) temp[pos] i;for (int i 0; i pos; i) if (!visited[temp[i]]) DFS(temp[i]);}void printMap() {for (int i 0; i n; i) {cout vertex[i];if (i n - 1) cout endl;else cout ;}for (int i 0; i n; i) {for (int j 0; j n; j) {cout array[i][j];if (j n - 1) cout endl;else cout ;}}cout partnumber endl;}~Map() {for (int i 0; i n; i) delete[]array[i];delete[]array;delete[]vertex;}
};int main() {int t;cin t;while (t--) {Map M;M.createMap();M.DFSTraverse();M.printMap();cout endl;}return 0;
}
题目二DS图 -- 最小生成树
题目描述
根据输入创建无向网。分别用Prim算法和Kruskal算法构建最小生成树。假设输入数据的最小生成树唯一。
输入要求
顶点数n
n个顶点
边数m
m条边信息,格式为顶点1顶点2权值
Prim算法的起点v
输出要求
输出最小生成树的权值之和
对两种算法按树的生长顺序输出边信息(Kruskal中边顶点按数组序号升序输出)
输入样例
6
v1 v2 v3 v4 v5 v6
10
v1 v2 6
v1 v3 1
v1 v4 5
v2 v3 5
v2 v5 3
v3 v4 5
v3 v5 6
v3 v6 4
v4 v6 2
v5 v6 6
v1输出样例
15
prim:
v1 v3 1
v3 v6 4
v6 v4 2
v3 v2 5
v2 v5 3
kruskal:
v1 v3 1
v4 v6 2
v2 v5 3
v3 v6 4
v2 v3 5
代码示例
#include iostream
#include string
#include cstring
#include iomanip
#include algorithm
#include cmath
#include queue
using namespace std;const int MAXNUMBER 100;struct Close {int adjvex;int loweight 0x3f3f3f3f;
} closedge[MAXNUMBER];struct Path {int head;int tail;
};class Map {int matrix[MAXNUMBER][MAXNUMBER] { 0 };string* vertex;int n;//顶点数int leastWeight 0;vectorPath path;int shortdis[MAXNUMBER];
public:Map() {cin n;vertex new string[n];for (int i 0; i n; i) cin vertex[i];for (int i 0; i n; i) shortdis[i] i;int edge;cin edge;for (int i 0; i edge; i) {string vex1, vex2;int weight;cin vex1 vex2 weight;matrix[find(vex1)][find(vex2)] matrix[find(vex2)][find(vex1)] weight;}}int find(string str) {for (int i 0; i n; i)if (vertex[i] str) return i;}void Prim() {string start_vertex;cin start_vertex;int start find(start_vertex);for (int i 0; i n; i) {if (matrix[start][i]) closedge[i] { start, matrix[start][i] };else closedge[i].adjvex start;}closedge[start].loweight 0;for (int i 1; i n; i) {int minWeight 0x3f3f3f3f, nextedge;for (int j 0; j n; j)if (minWeight closedge[j].loweight closedge[j].loweight) {minWeight closedge[j].loweight;nextedge j;}closedge[nextedge].loweight 0;Path p { closedge[nextedge].adjvex, nextedge };path.push_back(p);leastWeight minWeight;for (int j 0; j n; j)if (closedge[j].loweight matrix[nextedge][j] matrix[nextedge][j])closedge[j] { nextedge, matrix[nextedge][j] };}cout leastWeight endl;cout prim: endl;for (auto item : path)cout vertex[item.head] vertex[item.tail] matrix[item.head][item.tail] endl;}int get(int x) {if (shortdis[x] x) return x;return get(shortdis[x]);}void Kruskal() {path.clear();cout kruskal: endl;int cnt 0;for (int k 0; k n - 1; k) {int minWeight 0x3f3f3f3f, tail 0, head 0;for (int i 0; i n; i) {for (int j i 1; j n; j) {if (matrix[i][j] minWeight matrix[i][j] get(i) ! get(j)) {head i, tail j;minWeight matrix[i][j];}}}shortdis[get(tail)] get(head);Path p { head, tail };path.push_back(p);leastWeight minWeight;if (tail || head) cnt;}if (cnt n - 1) {//cout leastWeight endl;for (auto item : path) cout vertex[item.head] vertex[item.tail] matrix[item.head][item.tail] endl;}else cout -1 endl;}
};int main() {Map map;map.Prim();map.Kruskal();
}
题目三DS图 -- 汉密尔顿回路
题目描述
著名的“汉密尔顿Hamilton回路问题”是要找一个能遍历图中所有顶点的简单回路即每个顶点只访问 1 次。本题就要求你判断任一给定的回路是否汉密尔顿回路。
输入要求
首先第一行给出两个正整数无向图中顶点数 N2N≤200和边数 M。随后 M 行每行给出一条边的两个端点格式为“顶点1 顶点2”其中顶点从 1 到N 编号。再下一行给出一个正整数 K是待检验的回路的条数。随后 K 行每行给出一条待检回路格式为
n V1 V2 ⋯ Vn
其中 n 是回路中的顶点数Vi 是路径上的顶点编号。
输出要求
对每条待检回路如果是汉密尔顿回路就在一行中输出YES否则输出NO。
输入样例
6 10
6 2
3 4
1 5
2 5
3 1
4 1
1 6
6 3
1 2
4 5
6
7 5 1 4 3 6 2 5
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 3 4 5 2 6
7 6 1 2 5 4 3 1
输出样例
YES
NO
NO
NO
YES
NO
代码示例
#include iostream
#include string
#include cstring
#include iomanip
#include algorithm
#include cmath
#include queue
using namespace std;class Map {
private:int** array;int* vertex;int n;bool visited[20];int partnumber;
public:Map() {cin n;array new int* [n];for (int i 0; i n; i) {array[i] new int[n];for (int j 0; j n; j) array[i][j] 0;}vertex new int[n];for (int i 0; i n; i) vertex[i] i 1;partnumber 0;}int findIndex(int num) {for (int i 0; i n; i) if (num vertex[i]) return i;return -1;}void createMap() {int m, v1, v2;int num1, num2;cin m;for (int i 0; i m; i) {cin num1 num2;v1 findIndex(num1);v2 findIndex(num2);array[v1][v2] 1, array[v2][v1] 1;}}void DFSTraverse() {for (int i 0; i n; i) visited[i] false;for (int i 0; i n; i) {if (!visited[i]) {DFS(i);partnumber;}}}void DFS(int v) {visited[v] true;int* temp new int[n];int pos 0;for (int i 0; i n; i) if (array[v][i]) temp[pos] i;for (int i 0; i pos; i) if (!visited[temp[i]]) DFS(temp[i]);}void printMap() {for (int i 0; i n; i) {cout vertex[i];if (i n - 1) cout endl;else cout ;}for (int i 0; i n; i) {for (int j 0; j n; j) {cout array[i][j];if (j n - 1) cout endl;else cout ;}}cout partnumber endl;}void Hamilton() {int k;bool mark true;int cnt[20] { 0 };cin k;int head, tail;cin head;int start head;for (int i 1; i k; i) {cin tail;cnt[tail];if (i ! k - 1 tail start || cnt[tail] 2 tail ! start) mark false;if (!array[findIndex(head)][findIndex(tail)]){cout NO endl;continue;}head tail;if (start tail i k - 1 k n mark) cout YES endl;else if (start ! tail i k - 1 || k n i k - 1 || !mark i k - 1) cout NO endl;}}~Map() {for (int i 0; i n; i) delete[]array[i];delete[]array;delete[]vertex;}
};int main() {Map M;M.createMap();int t;cin t;while (t--) M.Hamilton();return 0;
}
题目四DS图 -- 六度空间
题目描述
“六度空间”理论又称作“六度分隔Six Degrees of Separation”理论。这个理论可以通俗地阐述为“你和任何一个陌生人之间所间隔的人不会超过六个也就是说最多通过五个人你就能够认识任何一个陌生人。”
“六度空间”理论虽然得到广泛的认同并且正在得到越来越多的应用。但是数十年来试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。
假如给你一个社交网络图请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入要求
输入第1行给出两个正整数分别表示社交网络图的结点数N表示人数、边数M≤33×N表示社交关系数。随后的M行对应M条边每行给出一对正整数分别是该条边直接连通的两个结点的编号节点从1到N编号。
输出要求
对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比精确到小数点后2位。每个结节点输出一行格式为“结点编号:空格百分比%”。
输入样例
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
输出样例
1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%
代码示例
#include iostream
#include string
#include cstring
#include iomanip
#include algorithm
#include cmath
#include queue
using namespace std;class Map {
private:int** array;int* vertex;int n;bool visited[20];int partnumber;int** reach;
public:Map() {cin n;array new int* [n];reach new int* [n];for (int i 0; i n; i) {array[i] new int[n];reach[i] new int[n];for (int j 0; j n; j) array[i][j] 0, reach[i][j] 0;}vertex new int[n];for (int i 0; i n; i) vertex[i] i 1;partnumber 0;}int findIndex(int num) {for (int i 0; i n; i) if (num vertex[i]) return i;return -1;}void createMap() {int m, v1, v2;int num1, num2;cin m;for (int i 0; i m; i) {cin num1 num2;v1 findIndex(num1);v2 findIndex(num2);array[v1][v2] 1, array[v2][v1] 1;}}void SDS() {for (int i 0; i n; i) {int number SDSBFS(i);cout i 1 : fixed setprecision(2) (double)number * 100 / n % endl;memset(visited, false, sizeof(visited));}}int SDSBFS(int i) {int cnt 0;int level 0, last i, tail -1;queueint q;visited[i] true;q.push(i);cnt;while (!q.empty()) {int k q.front();q.pop();for (int j 0; j n; j){if (j k) continue;if (!visited[j] array[k][j]) {q.push(j);tail j;visited[j] true;cnt;}}if (k last) level, last tail;if (level 6) break;}return cnt;}~Map() {for (int i 0; i n; i) delete[]array[i];delete[]array;delete[]vertex;}
};int main() {Map M;M.createMap();M.SDS();
}
题目五DS图 -- 红色警报
题目描述
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序当失去一个城市导致国家被分裂为多个无法连通的区域时就发出红色警报。注意若该国本来就不完全连通是分裂的k个区域而失去一个城市并不改变其他城市之间的连通性则不要发出警报。
输入要求
输入在第一行给出两个整数N0 N ≤ 500和M≤ 5000分别为城市个数于是默认城市从0到N-1编号和连接两城市的通路条数。随后M行每行给出一条通路所连接的两个城市的编号其间以1个空格分隔。在城市信息之后给出被攻占的信息即一个正整数K和随后的K个被攻占的城市的编号。
注意输入保证给出的被攻占的城市编号都是合法的且无重复但并不保证给出的通路没有重复。
输出要求
对每个被攻占的城市如果它会改变整个国家的连通性则输出Red Alert: City k is lost!其中k是该城市的编号否则只输出City k is lost.即可。如果该国失去了最后一个城市则增加一行输出Game Over.。
输入样例
5 4
0 1
1 3
3 0
0 4
5
1 2 0 4 3
输出样例
City 1 is lost.
City 2 is lost.
Red Alert: City 0 is lost!
City 4 is lost.
City 3 is lost.
Game Over.
代码示例
#include iostream
#include string
#include cstring
#include iomanip
#include algorithm
#include cmath
#include queue
using namespace std;class Map {
private:int** array;int* vertex;int n;bool visited[20];int partnumber;int** reach;int origin[20];
public:Map() {cin n;array new int* [n];reach new int* [n];for (int i 0; i n; i) {array[i] new int[n];reach[i] new int[n];for (int j 0; j n; j) array[i][j] 0, reach[i][j] 0;}vertex new int[n];for (int i 0; i n; i) vertex[i] i;partnumber 0;}int findIndex(int num) {for (int i 0; i n; i) if (num vertex[i]) return i;return -1;}void createMap() {int m, v1, v2;int num1, num2;cin m;for (int i 0; i m; i) {cin num1 num2;v1 findIndex(num1);v2 findIndex(num2);array[v1][v2] 1, array[v2][v1] 1;}}void RA() {memset(origin, 0, sizeof(visited));for (int i 0; i n; i) for (int j 0; j n; j) if (array[i][j]) origin[i];int x;cin x;while (x--) {int y;cin y;int tozerocnt 0;for (int i 0; i n; i) if (array[y][i]) array[y][i] 0, array[i][y] 0;int cur[20] { 0 };for (int i 0; i n; i) {for (int j 0; j n; j) if (array[i][j]) cur[i];}for (int i 0; i n; i) {if (origin[i] ! 0 cur[i] 0) tozerocnt;origin[i] cur[i];}if (tozerocnt 1) cout Red Alert: City y is lost! endl;else cout City y is lost. endl;}cout Game Over. endl;}~Map() {for (int i 0; i n; i) delete[]array[i];delete[]array;delete[]vertex;}
};int main() {Map M;M.createMap();M.RA();
}
