wordpress是模板建站,asp电影网站源码,网站要怎么做吸客户引眼球,dw做网站有雪花效果A. 图综合练习--构建邻接表
题目描述
已知一有向图#xff0c;构建该图对应的邻接表。
邻接表包含数组和单链表两种数据结构#xff0c;其中每个数组元素也是单链表的头结点#xff0c;数组元素包含两个属性#xff0c;属性一是顶点编号info#xff0c;属性二是指针域n…A. 图综合练习--构建邻接表
题目描述
已知一有向图构建该图对应的邻接表。
邻接表包含数组和单链表两种数据结构其中每个数组元素也是单链表的头结点数组元素包含两个属性属性一是顶点编号info属性二是指针域next指向与它相连的顶点信息。
单链表的每个结点也包含两个属性属性一是顶点在数组的位置下标属性二是指针域next指向下一个结点。
输入
第1行输入整数t表示有t个图
第2行输入n和k表示该图有n个顶点和k条弧。
第3行输入n个顶点。
第4行起输入k条弧的起点和终点连续输入k行
以此类推输入下一个图
输出
输出每个图的邻接表每行输出格式数组下标 顶点编号-连接顶点下标-......-^数组下标从0开始。
具体格式请参考样例数据每行最后加入“^”表示NULL。
样例查看模式
正常显示查看格式
输入样例1
1\n 5 7\n A B C D E\n A B\n A D\n A E\n B D\n C B\n C E\n E D\n
输出样例1
0 A-1-3-4-^\n 1 B-3-^\n 2 C-1-4-^\n 3 D-^\n 4 E-3-^\n
AC代码
#includeiostream
#includevector
#includemap
using namespace std;
class graph
{int n, k;vectorinth;vectorintne;vectorinte;int idx;mapchar, intid;vectorcharvalue;
public:graph(){idx 0;cin n k;h.resize(2 * n, -1);ne.resize(2 * n);e.resize(2 * n);for (int i 0; i n; i){char c;cin c;id[c] i;value.push_back(c);}for (int i 0; i k; i){char u, v;cin u v;add(id[u], id[v]);}}void add(int a, int b){e[idx] b;ne[idx] h[a];h[a] idx;}void show(){for (int i 0; i n; i){cout i value[i] -;vectorintans;for (int j h[i]; ~j; j ne[j]){int k e[j];ans.push_back(id[value[k]]);}//由于本题使用头插法而此方法是尾插法故要逆转for (int ians.size()-1;i0;i--){cout ans[i] -;}cout ^ endl;}}
};
int main()
{int t;cin t;while (t--){graph g;g.show();}return 0;
}
B. DS图—图的邻接矩阵存储及度计算
题目描述
假设图用邻接矩阵存储。输入图的顶点信息和边信息完成邻接矩阵的设置并计算各顶点的入度、出度和度并输出图中的孤立点度为0的顶点
--程序要求--
若使用C只能include一个头文件iostream若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件不看代码作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
测试次数T每组测试数据格式如下
图类型 顶点数 D—有向图U—无向图
顶点信息
边数
每行一条边顶点1 顶点2或弧弧尾 弧头信息
输出
每组测试数据输出如下信息具体输出格式见样例
图的邻接矩阵
按顶点信息输出各顶点的度无向图或各顶点的出度 入度 度有向图。孤立点的度信息不输出。
图的孤立点。若没有孤立点不输出任何信息。
样例查看模式
正常显示查看格式
输入样例1
2\n D 5\n V1 V2 V3 V4 V5\n 7\n V1 V2\n V1 V4\n V2 V3\n V3 V1\n V3 V5\n V4 V3\n V4 V5\n U 5\n A B C D E\n 5\n A B\n A C\n B D\n D C\n A D
输出样例1
0 1 0 1 0\n 0 0 1 0 0\n 1 0 0 0 1\n 0 0 1 0 1\n 0 0 0 0 0\n V1: 2 1 3\n V2: 1 1 2\n V3: 2 2 4\n V4: 2 1 3\n V5: 0 2 2\n 0 1 1 1 0\n 1 0 0 1 0\n 1 0 0 1 0\n 1 1 1 0 0\n 0 0 0 0 0\n A: 3\n B: 2\n C: 2\n D: 3\n E
AC代码
#includeiostream
using namespace std;
//输入测试次数每组测试
//图类型顶点数
//顶点信息边数每条边的头尾
//输出每个点的出度和入度单独输出孤立点
class Map
{int vertexnum;string* vertex;int** adjmatrix;char kind;
public:Map(){cin kind vertexnum;vertex new string[vertexnum];for (int i 0; i vertexnum; i){cin vertex[i];}adjmatrix new int* [vertexnum];for (int i 0; i vertexnum; i){adjmatrix[i] new int[vertexnum];for (int j 0; j vertexnum; j){adjmatrix[i][j] 0;}}int n;cin n;for (int i 0; i n; i){string s1, s2;cin s1 s2;int index1 0;int index2 0;for (int j 0; j vertexnum; j){if (vertex[j] s1){index1 j;break;}}for (int j 0; j vertexnum; j){if (vertex[j] s2){index2 j;break;}}switch (kind){case U:adjmatrix[index2][index1] 1;case D:adjmatrix[index1][index2] 1;default:break;}}}void display_array(){for (int i 0; i vertexnum; i){cout adjmatrix[i][0];for (int j 1; j vertexnum; j){cout adjmatrix[i][j];}cout endl;}}void display_node(){if (kind U){for (int i 0; i vertexnum; i){int cnt 0;for (int j 0; j vertexnum; j){if (adjmatrix[i][j] ! 0){cnt;}}if (cnt){cout vertex[i] : cnt endl;}else{cout vertex[i] endl;}}}else if (kind D){for (int i 0; i vertexnum; i){int cnt1 0;for (int j 0; j vertexnum; j){if (adjmatrix[i][j] ! 0){cnt1;}}int cnt2 0;for (int j 0; j vertexnum; j){if (adjmatrix[j][i] ! 0){cnt2;}}if (cnt1 || cnt2)//存在其中一个就不是孤立点{cout vertex[i] : cnt1 cnt2 cnt1 cnt2 endl;}else{cout vertex[i] endl;}}}}~Map(){delete[]vertex;for (int i 0; i vertexnum; i){delete[]adjmatrix[i];}delete[]adjmatrix;}
};
int main()
{int n;cin n;while (n--){Map m;m.display_array();m.display_node();}return 0;
}
C. DS图遍历--深度优先搜索
题目描述
给出一个图的邻接矩阵对图进行深度优先搜索从顶点0开始
代码框架参考课本P169算法7.4和7.5同学们可在理解的基础上自行设计算法不强制要求完全相同
注意图n个顶点编号从0到n-1
输入
第一行输入t表示有t个测试实例
第二行输入n表示第1个图有n个结点
第三行起每行输入邻接矩阵的一行以此类推输入n行
第i个结点与其他结点如果相连则为1无连接则为0数据之间用空格隔开
以此类推输入下一个示例
输出
每行输出一个图的深度优先搜索结果结点编号之间用空格隔开
样例查看模式
正常显示查看格式
输入样例1
2\n 4\n 0 0 1 1\n 0 0 1 1\n 1 1 0 1\n 1 1 1 0\n 5\n 0 0 0 1 1\n 0 0 1 0 0\n 0 1 0 1 1\n 1 0 1 0 0\n 1 0 1 0 0\n
输出样例1
0 2 1 3 \n 0 3 2 1 4 \n
AC代码
#includebits/stdc.h
using namespace std;
int main()
{int t;cin t;while (t--){int n;cin n;vectorvectorintv(n);for (int i 0; i n; i){for (int j 0; j n; j){int x;cin x;v[i].push_back(x);}}vectorintst(n);//标记是否已经走过stackints;//深度优先搜索使用栈for (int i 0; i n; i)//每个结点都要搜一次确定每个都走过{if (st[i])continue;s.push(i);while (!s.empty())//每个点开始搜{auto t s.top();s.pop();if (st[t])continue;st[t] 1;cout t ;//满足条件可以搜//注意逆序枚举连接点//因为是栈先进去后出来for (int j n - 1; j 0; j--){if (v[t][j] !st[j]){s.push(j);}}}}cout endl;}return 0;
}
D. DS图遍历--广度优先搜索
题目描述
给出一个图的邻接矩阵对图进行广度优先搜索从顶点0开始
注意图n个顶点编号从0到n-1
输入
第一行输入t表示有t个测试实例
第二行输入n表示第1个图有n个结点
第三行起每行输入邻接矩阵的一行以此类推输入n行
第i个结点与其他结点如果相连则为1无连接则为0数据之间用空格隔开
以此类推输入下一个示例
输出
每行输出一个图的广度优先搜索结果结点编号之间用空格隔开
样例查看模式
正常显示查看格式
输入样例1
2\n 4\n 0 0 1 1\n 0 0 1 1\n 1 1 0 1\n 1 1 1 0\n 5\n 0 0 0 1 1\n 0 0 1 0 0\n 0 1 0 1 1\n 1 0 1 0 0\n 1 0 1 0 0\n
输出样例1
0 2 3 1 \n 0 3 4 2 1 \n
AC代码
#includebits/stdc.h
using namespace std;
int main()
{int t;cin t;while (t--){int n;cin n;vectorvectorintv(n);for (int i 0; i n; i){for (int j 0; j n; j){int x;cin x;v[i].push_back(x);}}vectorintst(n);//标记是否已经走过queueints;//广度搜索使用队列for (int i 0; i n; i)//每个结点都要搜一次确定每个都走过{if (st[i])continue;s.push(i);while (!s.empty())//每个点开始搜{auto t s.front();s.pop();if (st[t])continue;st[t] 1;cout t ;//满足条件可以搜//注意顺序枚举连接点//因为是队列先进去先出来for (int j 0; jn-1;j){if (v[t][j] !st[j]){s.push(j);}}}}cout endl;}return 0;
}
E. DS图—图非0面积
题目描述
编程计算由1围成的下列图形的面积。面积计算方法是统计1所围成的闭合曲线中0点的数目。如图所示在10*10的二维数组中1围住了15个点因此面积为15。 提示queue
输入
测试次数t
每组测试数据格式为
数组大小m,n
一个由0和1组成的m*n的二维数组
输出
对每个二维数组输出符号1围住的0的个数即围成的面积。假设一定有1组成的闭合曲线但不唯一。
样例查看模式
正常显示查看格式
输入样例1
2\n 10 10\n 0 0 0 0 0 0 0 0 0 0\n 0 0 0 0 1 1 1 0 0 0\n 0 0 0 0 1 0 0 1 0 0\n 0 0 0 0 0 1 0 0 1 0\n 0 0 1 0 0 0 1 0 1 0\n 0 1 0 1 0 1 0 0 1 0\n 0 1 0 0 1 1 0 1 1 0\n 0 0 1 0 0 0 0 1 0 0\n 0 0 0 1 1 1 1 1 0 0\n 0 0 0 0 0 0 0 0 0 0\n 5 8\n 0 1 1 0 0 1 1 0\n 1 0 1 0 1 0 0 1\n 0 1 0 1 0 0 1 0\n 0 1 0 0 1 1 1 0\n 0 0 0 0 0 0 0 0\n
输出样例1
15\n 5\n
#includebits/stdc.h
using namespace std;
int n,m;
int dx[]{1,-1,0,0};
int dy[]{0,0,-1,1};
vectorvectorintv;
void dfsfind(int x,int y)
{if(x0||y0||xm||yn||v[x][y])return;v[x][y]1;for(int i0;i4;i){dfsfind(xdx[i],ydy[i]);}
}
int main()
{int t;cint;while(t--){v.clear();cinmn;v.resize(m);for(int i0;im;i){for(int j0;jn;j){int x;cinx;v[i].push_back(x);}}int ans0;for(int i0;im;i)//先按行{dfsfind(i,0);dfsfind(i,n-1);}for(int i0;in;i)//后按列{dfsfind(0,i);dfsfind(m-1,i);}for(int i0;im;i){for(int j0;jn;j){if(v[i][j]0)ans;}}coutansendl;}return 0;
}
F. 社交网络图中结点的“重要性”计算
题目描述
在社交网络中个人或单位结点之间通过某些关系边联系起来。他们受到这些关系的影响这种影响可以理解为网络中相互连接的结点之间蔓延的一种相互作用可以增强也可以减弱。而结点根据其所处的位置不同其在网络中体现的重要性也不尽相同。
“紧密度中心性”是用来衡量一个结点到达其它结点的“快慢”的指标即一个有较高中心性的结点比有较低中心性的结点能够更快地平均意义下到达网络中的其它结点因而在该网络的传播过程中有更重要的价值。在有N个结点的网络中结点vi的“紧密度中心性”Cc(vi)数学上定义为vi到其余所有结点vj (ji) 的最短距离d(vi,vj)的平均值的倒数
对于非连通图所有结点的紧密度中心性都是0。
给定一个无权的无向图以及其中的一组结点计算这组结点中每个结点的紧密度中心性。
输入
输入第一行给出两个正整数N和M其中N≤104是图中结点个数顺便假设结点从1到N编号M≤105是边的条数。随后的M行中每行给出一条边的信息即该边连接的两个结点编号中间用空格分隔。最后一行给出需要计算紧密度中心性的这组结点的个数K≤100以及K个结点编号用空格分隔。
输出
按照Cc(i)x.xx的格式输出K个给定结点的紧密度中心性每个输出占一行结果保留到小数点后2位。
样例查看模式
正常显示查看格式
输入样例1
9 14\n 1 2\n 1 3\n 1 4\n 2 3\n 3 4\n 4 5\n 4 6\n 5 6\n 5 7\n 5 8\n 6 7\n 6 8\n 7 8\n 7 9\n 3 3 4 9
输出样例1
Cc(3)0.47\n Cc(4)0.62\n Cc(9)0.35
AC代码
#includebits/stdc.h
using namespace std;
//求一个点到其余各点的最短路-FLoyd
const int N 1000, inf 1e9;
long long res 0;
int n, m, k;
int d[N][N];
void floyd()
{for (int k 1; k n; k)//中间点枚举放在首个循环{for (int i 1; i n; i){for (int j 1; j n; j){d[i][j] min(d[i][j], d[i][k] d[k][j]);}}}
}
int main()
{cin n m;//注意弗洛伊德的初始for (int i 1; i n; i){for (int j 1; j n; j){if (i j)d[i][j] 0;else d[i][j] inf;}}for (int i 0; i m; i){int a, b;cin a b;d[a][b] d[b][a] 1;//无向图}floyd();bool flag 0;cin k;for (int i 0; i k; i) {res 0;int x;cin x;if (!flag){for (int j 1; j n; j){if (x j)continue;if (d[x][j] inf / 2)//此时不连通{flag 1;break;}res d[x][j];}}if (flag)printf(Cc(%d)0.00\n, x);//无法满足到其余所有点else{double ans (double)(n - 1) / res;printf(Cc(%d)%.2lf\n, x, ans);}}return 0;
}
