图论题目集一（代码 注解）

目录

题目一： 

题目二：

题目三：

题目四：

题目五：

题目六：

题目七：

题目一： 

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int g[15][15], vis[15] = { 0 };
int n, m;
queue<int> q;
void dfs(int k)//深度
{
    cout << k << " ";
    vis[k] = 1;
    for (int i = 0; i < n; i++)
    {
        if (i == k)
            continue;
        if (vis[i] == 0 && g[k][i])
        {
            dfs(i);
        }
    }
    return;
}
void bfs(int k)//广度
{
    q.push(k);
    while (!q.empty())
    {
        k = q.front();
        q.pop();
        if(vis[k]==0)
        {
            cout<<k<<" ";
            vis[k]=1;
        }
        for (int i = 0; i < n; i++)
        {
            if (vis[i] == 0 && g[k][i] == 1)
            {
                q.push(i);
            }
        }
    }
    return;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)//构建邻接矩阵
    {
        int x, y;
        cin >> x >> y;
        g[x][y] = 1, g[y][x] = 1;
    }
    for (int i = 0; i < n; i++)//深度
    {
        if (vis[i] == 0)
        {
            cout << "{ ";
            dfs(i);
            cout << "}" << endl;
        }
    }
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++)//广度
    {
        if(vis[i]==0)
        {
            cout << "{ ";
            bfs(i);
            cout << "}" << endl;
        }
    }
}

 题目二：

#include<iostream>
#include<algorithm>
using namespace std;
int g[10005][10005];
float n, k;
typedef struct node
{
	int data;
	int w = 0;
}node;
void warshall()//传递闭包
{
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				if (g[i][k] && g[k][j])//连通
				{
					if (i == j)
						continue;
					if (g[i][j] == 0 || g[i][j] > g[i][k] + g[k][j])//没有直接连通或者新通路距离小于之前通路
						g[i][j] = g[i][k] + g[k][j];
				}
			}
}
bool cmp(node a, node b)
{
	return a.w < b.w;
}
int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			g[i][j] = 0;
	for (int i = 0; i < k; i++)//无向图，初始距离都为1
	{
		int v1, v2;
		cin >> v1 >> v2;
		g[v1][v2] = 1;
		g[v2][v1] = 1;
	}
	warshall();
	/*for (int i = 1; i <= n; i++)//输出邻接矩阵
	{
		for (int j = 1; j <= n; j++)
			cout << g[i][j] << " ";
		cout << endl;
	}*/
	float ans[10005] ;
	for (int i = 1; i <= n; i++)
	{
		ans[i] = 0;
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
				ans[i]++;
			if (g[i][j]>0 && g[i][j] <= 6)//符合条件
				ans[i]++;
		}
	}
	for (int i = 1; i <= n; i++)
		printf("%d:% .2f%%\n", i, ans[i] / n * 100);
}

题目三：

#include<iostream>
using namespace std;
int g[1010][1010];
int n,m,s;
int vis[1010];
int path[1010];
int cnt=0;
void dfs(int k)//深度
{
    //cout<<k<<" ";
        path[cnt++]=k;//记录去的路径
    vis[k]=1;
    for(int i=0;i<=n;i++)
    {
        if(i==k)
            continue;
        if(vis[i]==0&&g[k][i]==1)
        {
            dfs(i);
            path[cnt++]=k;//记录回的路径
        }
    }
    return ;
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)//构建邻接矩阵
    {
        int x,y;
        cin>>x>>y;
        g[x][y]=g[y][x]=1;
    }
    dfs(s);
    int flag=1;//标记是否可以遍历完所有
    for(int i=1;i<=n;i++)//查询是否遍历完所有
    {
        if(vis[i]==0)
        {
           flag=0;
            break;
        }
    }
    if(flag==1)//输出序列
    {
        for(int i=0;i<cnt;i++)
        {
            cout<<path[i];
            if(i!=cnt-1)
                cout<<" ";
        }
    }
    else
    {
        for(int i=0;i<cnt;i++)
            cout<<path[i]<<" ";
        cout<<0;
    }
}

题目四：

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 10, M = 1e6 + 10, inf = 1e14;
struct  node
{
    ll v, w;
    bool operator <(const node& y) const//重载一个<,用于优先队列排序
    {
        return w > y.w;//小到大
    }
};
int n, m, t;
priority_queue<node>q;
vector<node> e[N];
ll dis[N], vis[N];
void Dij(int t)
{
    dis[t] = 0;//从t号点出发，表示从t到t距离为0
    q.push({ t,dis[t] });//t号点以及到t的距离入队
    while (q.size())
    {
        int u = q.top().v;//取最小边相连的点出队
        q.pop();
        if (vis[u])//访问过则跳过
            continue;
        vis[u] = 1;//没访问赋为访问
        for (auto i : e[u])//遍历以u为出发点的边
        {
            int v = i.v, w = i.w;//取其相连的点及权值
            if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新
            {
                dis[v] = dis[u] + w;
                q.push({ v,dis[v] });//v点以及到v的距离
            }
        }
    }

}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, w=1;
        cin >> x >> y;
        e[x].push_back({ y,w });//存入以x出发到y，权值为w
        e[y].push_back({ x,w });//存入以x出发到y，权值为w
    }
    int N;
    cin >> N;
    while (N--)
    {
        cin >> t;
        float ans = 0,sum=0;
        memset(dis, 0x3f3f3f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        Dij(t);//从t点出发
        for (int i = 1; i <= n; i++)
        {
            sum += dis[i];//求和
        }
        //cout << sum;
        ans = (n - 1) /sum;
        printf("Cc(%d)=%.2f\n", t, ans);
    }
}

题目五：

#include<iostream>//并查集
using namespace std;
int fa[204], mp[102][102];
int find(int x)//查找
{
    if(fa[x]==x)  return x;
    return fa[x]=find(fa[x]);
}
void Merge(int x, int y)//合并
{
    int a=find(x), b=find(y);
    if(a==b) return;
    else fa[a]=fa[b];
}
int main()
{
    int n, m, k;
    cin>>n>>m>>k;
    int a, b, c;
    for(int i=1;i<=n;i++)//初始化
        fa[i]=i;
    for(int i=0; i<m; i++)
    {
        cin>>a>>b>>c;
        mp[a][b]=c,mp[b][a]=c;
        if(c==1)//为朋友则合并，因为朋友的朋友也是朋友
            Merge(a, b);
    }
    for(int i=0; i<k; i++)
    {
        cin>>a>>b;
        if(mp[a][b]==1) cout<<"No problem"<<endl;
        else if(mp[a][b]==-1)//是敌对关系
        {
            if(find(a)==find(b))    cout<<"OK but..."<<endl;//但是有相同的朋友，即在一个集合内
            else cout<<"No way"<<endl;
        }
        else cout<<"OK"<<endl;
    }
    return 0;
}

题目六：

#include<iostream>
using namespace std;
int n, m, mp[520][520], f[520];
void init() //初始化
{
	for (int i = 0; i < n; i++)
		f[i] = i;
}
int find(int x) //查询
{
	if (x == f[x]) return x;
	return f[x] = find(f[x]);
}
void merge(int x, int y)//合并 
{
	int xx = find(x);
	int yy = find(y);
	if (xx != yy) f[xx] = yy;
	return;
}
int sum()//统计连通块个数
{
	int cnt = 0;
	for (int i = 0; i < n; i++) //统计连通块个数 
	{
		if (i == find(i)) cnt++;
	}
	return cnt;
}
int main() 
{
	int a, b, k, x, cnt = 0, cnt2, flag = 0;
	cin >> n >> m;
	init();
	while (m--) 
	{
		cin >> a >> b;
		mp[a][b] = 1;
		mp[b][a] = 1;
		merge(a, b);
	}
	cin >> k;
	cnt = sum();
	if (k == n) flag = 1; //要输出Game Over; 
	while (k--) 
	{
		cin >> x;
		init();
		cnt2 = 0;  //x去掉后的连通区域个数 
		for (int i = 0; i < n; i++) 
			mp[x][i] = mp[i][x] = 0;
		for (int i = 0; i < n; i++) 
		{
			for (int j = 0; j < n; j++)
			{
				if (mp[i][j]) merge(i, j);
			}
		}
		cnt2 = sum();
		if (cnt2 < cnt + 2) cout << "City " << x << " is lost." << endl;
		else cout << "Red Alert: City " << x << " is lost!" << endl;//1、去掉i点后，一个连通块至少被分为两个，增加了一个
		cnt = cnt2;                                                 //2、去掉i点后，再次统计cnt2时，就会把去掉的点i也加上，所以要大于cnt+1
		
	}
	if (flag) cout << "Game Over." << endl;
}

题目七：

#include<iostream>
#include<queue>
using namespace std;
int n, id, fa, ma, k;
int f[10100], peo[10100], avgs[10100], avga[10100],st[10100];
struct node
{
	int a, b;
}e[10100];
struct family
{
	int id, peo, avgs, avga;
	bool operator<(const family& x)const
	{
		if (x.peo * avga == peo * x.avga)//人均相等,则升序排序
			return id > x.id;
		return x.peo * avga < peo * x.avga;//人均多的在前
	}
};
int find(int x)//查找
{
	if (f[x] == x) return x;
	return f[x] = find(f[x]);
}
void meger(int x, int y)//合并
{
	x = find(x), y = find(y);
	if (x != y)
	{
		f[max(x, y)] = min(x, y);//小号id的设为父亲
		peo[min(x, y)] += peo[max(x, y)];//家庭人数加到小号id
		avgs[min(x, y)] += avgs[max(x, y)];//房屋数量加到小号id
		avga[min(x, y)] += avga[max(x, y)];//服务面积加到小号面积

	}
}
int main()
{
	for (int i = 0; i < 10100; i++) f[i] = i, peo[i] = 1;//初始化，每个父亲节点是自己，自己家庭都有一个自己
	cin >> n;
	int count = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> id >> fa >> ma >> k;
		if (fa != -1) e[count++] = { id,fa };//存关系
		if (ma != -1) e[count++] = { id,ma };//存关系
		st[id] = 1;//存在这个人
		int kid;
		for (int j = 1; j <= k; j++)
		{
			cin >> kid;
			e[count++] = { id,kid };//存关系
		}
		cin >> avgs[id] >> avga[id];
	}
	for (int i = 0; i < count; i++)//合并家庭
	{
		int a = e[i].a, b = e[i].b;
		st[a] = st[b] = 1;
		meger(a, b);//合并二者为一个家庭
	}
	priority_queue<family>ans;//优先队列
	for (int i = 0; i < 10100; i++)
	{
		if (st[i] && f[i] == i)//这个人存在且父亲节点是自己
			ans.push({ i,peo[i],avgs[i],avga[i] });
	}
	//count << st[8888] << f[8888];
	cout << ans.size() << endl;
	while (!ans.empty())
	{
		family t = ans.top();
		ans.pop();
		printf("%04d %d %.3lf %.3lf\n", t.id, t.peo, (double)t.avgs / t.peo, (double)t.avga / t.peo);
	}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/467082.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

python实现大图片切割和合并验证切割是否正确

python实现大图片切割和合并验证切割是否正确

在目标检测中，有时候拍摄的图像较大，而待测目标只是整个图像的一小块区域，这时候就需要对大的图像进行分割，这样有助于深度学习模型训练的速度，以及推理的速度，所以我们在拿到大的图像的时候先对其进行分割，分割成几个小区域，根据我们的训练模型输入图片大小来确定所要…
阅读更多...
Vue.js+SpringBoot开发食品生产管理系统

Vue.js+SpringBoot开发食品生产管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 加工厂管理模块2.2 客户管理模块2.3 食品管理模块2.4 生产销售订单管理模块2.5 系统管理模块2.6 其他管理模块 三、系统展示四、核心代码4.1 查询食品4.2 查询加工厂4.3 新增生产订单4.4 新增销售订单4.5 查询客户 五、…
阅读更多...
VBA技术资料MF131：代码执行过程中实现毫秒等待

VBA技术资料MF131：代码执行过程中实现毫秒等待

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套&#xff0c;分为初级、中级、高级三大部分&#xff0c;教程是对VBA的系统讲解&#…
阅读更多...
代码随想录算法训练营第11天| 20. 有效的括号，1047. 删除字符串中的所有相邻重复项，150. 逆波兰表达式求值

代码随想录算法训练营第11天| 20. 有效的括号，1047. 删除字符串中的所有相邻重复项，150. 逆波兰表达式求值

系列文章目录 目录 系列文章目录20. 有效的括号利用栈对称匹配将栈中元素弹出与判断栈顶元素是否匹配分开&#xff0c;比较耗时&#xff08;2ms)&#xff1a;若将栈中元素弹出与判断栈顶元素是否匹配放一起&#xff0c;比较节省时间(1ms)&#xff1a; 1047. 删除字符串中的所有…
阅读更多...
计算机视觉之三维重建（1）---摄像机几何

计算机视觉之三维重建（1）---摄像机几何

文章目录 一、针孔模型和透镜1.1 针孔摄像机1.2 近轴折射模型1.3 透镜问题 二、摄像机几何2.1 像平面和像素平面2.2 齐次坐标下的投影变换2.3 摄像机倾斜2.4 规范化摄像机2.5 世界坐标系2.6 Faugeras定理2.7 投影变换性质&#xff1a; 三、其他投影摄像机模型3.1 弱透视投影摄像…
阅读更多...
【小白笔记：JetsonNano学习（二）JetsonNano 安装开机问题屏幕进不去】

【小白笔记：JetsonNano学习（二）JetsonNano 安装开机问题屏幕进不去】

重新烧录sd卡后插入Jetson Nano后出现的界面显示烧录失败&#xff0c;如下所示&#xff1a; 将经过烧录之后的sd卡插入jetson nano之后出现以下的几个界面&#xff0c;表示烧录失败。 原因分析&#xff1a;烧录的tf卡为sd卡时候的格式化的格式不对&#xff0c;新建格式出错&am…
阅读更多...
万界星空科技漆包线工厂生产管理软件

万界星空科技漆包线工厂生产管理软件

今天就说说漆包线行业&#xff0c;漆包线是工业电机&#xff08;包括电动机和发电机&#xff09;、变压器、电工仪表、电力及电子元器件、电动工具、家用电器、汽车电器等用来绕制电磁线圈的主要材料。 产业结构调整加快&#xff0c;技术升级和需求多样化是推动漆包线加快产业…
阅读更多...
c语言基础~函数详解

c语言基础~函数详解

前言 今天我们来学习一波函数的概念,帮助各位理解函数,本次博客取自一些书籍以及各大网站的讲解,把它整合在一起并且详细讲解 1函数的理解 我们得知道什么是函数&#xff0c;函数的作用是什么,好不会表述没关系&#xff0c;我们翻书 c primer plus 是这么说的"函数是指…
阅读更多...
【JAVA】Servlet开发

【JAVA】Servlet开发

目录 HttpServlet HttpServletRequest HttpServletResponse 错误页面 设置网页自动刷新时间 构造重定向相应 js发起http请求 服务器端对js发起的http请求进行处理 前端获取后端数据&#xff0c;添加到当前页面的末尾&#xff0c;代码示例&#xff1a; 前后端交互&…
阅读更多...
24计算机考研调剂 | 【官方】山东师范大学（22自命题）

24计算机考研调剂 | 【官方】山东师范大学（22自命题）

山东师范大学2024年拟接收调剂 考研调剂信息 调剂专业目录如下&#xff1a; 计算机技术&#xff08;085404&#xff09;、软件工程&#xff08;085405&#xff09; 补充内容 我校2024年硕士研究生调剂工作将于4月8日教育部“中国研究生招生信息网”&#xff08;https://yz.ch…
阅读更多...
如何使用代理IP进行口子查和渠道查：代理IP使用方法

如何使用代理IP进行口子查和渠道查：代理IP使用方法

在进行问卷调查时&#xff0c;为了避免被限制访问或被封禁IP&#xff0c;使用代理IP已经成为了必要的选择。 其中&#xff0c;口子查和渠道查也不例外。 使用代理IP可以隐藏本机IP地址&#xff0c;模拟不同的IP地址&#xff0c;从而规避被封禁的风险。但是&#xff0c;对于很…
阅读更多...
3.Gen＜I＞Cam文件配置

3.Gen＜I＞Cam文件配置

Gen<I>Cam踩坑指南 我使用的是大恒usb相机&#xff0c;第一步到其官网下载大恒软件安装包,安装完成后图标如图所示&#xff0c;之后连接相机&#xff0c;打开软件&#xff0c;相机显示一切正常。之后查看软件的安装目录如图&#xff0c;发现有GenICam和GenTL两个文件&am…
阅读更多...
2024全新红娘交友系统定制版源码 | 相亲交友小程序源码 全开源可二开

2024全新红娘交友系统定制版源码 | 相亲交友小程序源码 全开源可二开

内容目录 一、详细介绍二、效果展示1.部分代码2.效果图展示 三、学习资料下载 一、详细介绍 全新红娘交友系统定制版源码 | 相亲交友小程序源码 全开源可二开 定制版红娘交友平台小程序源码&#xff0c;很牛逼的东西&#xff0c;虽然是小程序&#xff0c;但是有700多M大&…
阅读更多...
【办公类-22-11】周计划系列（5-3）“周计划-03 周计划内容循环修改“ （2024年调整版本）

【办公类-22-11】周计划系列（5-3）“周计划-03 周计划内容循环修改“ （2024年调整版本）

背景需求&#xff1a; 前文从原来的“新模版”文件夹里提取了周计划主要内容和教案内容。 【办公类-22-10】周计划系列&#xff08;5-2&#xff09;“周计划-02源文件docx读取5天“ &#xff08;2024年调整版本&#xff09;-CSDN博客文章浏览阅读1.1k次&#xff0c;点赞29次&…
阅读更多...
苍穹外卖-day10：Spring Task、订单状态定时处理、来单提醒（WebSocket的应用）、客户催单（WebSocket的应用）

苍穹外卖-day10：Spring Task、订单状态定时处理、来单提醒（WebSocket的应用）、客户催单（WebSocket的应用）

苍穹外卖-day10 课程内容 Spring Task订单状态定时处理WebSocket来单提醒客户催单 功能实现&#xff1a;订单状态定时处理、来单提醒和客户催单 订单状态定时处理&#xff1a; 来单提醒&#xff1a; 客户催单&#xff1a; 1. Spring Task 1.1 介绍 Spring Task 是Spring框…
阅读更多...
el-form 的表单校验，如何验证某一项或者多项；validateField 的使用

el-form 的表单校验，如何验证某一项或者多项；validateField 的使用

通常对form表单的校验都是整体校验&#xff1a; this.$refs.form.validate( valid > {if (valid) {// 校验通过&#xff0c;业务逻辑代码...} }); 如果需要对表单里的特定一项或几项进行校验&#xff0c;应该如何实现&#xff1f; 业务场景&#xff1a;下图点探测按钮时…
阅读更多...
高精度计算

高精度计算

主页&#xff1a;(*∇&#xff40;*) 咦,又好了~ xiaocr_blog &#xff08;1&#xff09;数据的接收方法和存储方法: 当输入的数据很长的时候&#xff0c;可采取字符串方式输入&#xff0c;这样可以输入位数很长的数&#xff0c;利用字符串函数和操作运算&#xff0c;将每一位…
阅读更多...
复杂网络——半局部中心法

复杂网络——半局部中心法

一、概述 由于最近写论文需要使用复杂网络知识中的半局部中心法&#xff0c;但是截止目前来说&#xff0c;网上几乎搜索不到有关的MATLAB程序代码&#xff0c;只有一篇用Python编写的程序&#xff0c;我的电脑中没有python&#xff0c;所以我花费一些时间&#xff0c;利用matla…
阅读更多...
Excel数据可视化

Excel数据可视化

饼图 1、选中数据----点击插入----点击饼图 2、更改数据标签&#xff08;修改标题名直接改就行&#xff09; 柱形图 1、选中数据、点击插入二维柱形图 坐标轴问题----切换行和列 如何将横轴变成想要的4、5、6、7月&#xff1f; &#xff08;1&#xff09;右键----选择数据 -…
阅读更多...
计算机二级（Python）真题讲解每日一题：《十字叉》

计算机二级（Python）真题讲解每日一题：《十字叉》

描述‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬ ‪‬‪‬‪‬‪‬‪‬‮‬‪…
阅读更多...
最新文章

Copyright @ 2022~2023