首页 > 其他分享 >关系网络

关系网络

时间:2023-04-25 19:35:17浏览次数:29  
标签:关系 表示 队列 认识 bh 网络 int 101

有n个人,他们的编号为1~n,其中有一些人相互认识,现在x想要认识y,可以通过他所认识的人来认识更多的人(如果a认识b,b认识c那么a可以通过b来认识c),求出x最少需要通过多少人才能认识y。

输入

  • 第1行3个整数n、x、y,2≤n≤100;
  • 接下来的n行是一个nXn的邻接矩阵,a[i][j]=1表示i认识j,a[i][j]=0表示不认识。保证i=j时,a[i][j]=0,并且a[i][j]=a[j][i]。

输出

  • 一行一个整数,表示x认识y最少需要通过的人数。数据保证x一定能认识y

样例输入

5 1 5
0 1 0 0 0
1 0 1 1 0
0 1 0 1 0
0 1 1 0 1
0 0 0 1 0

样例输出

2



#include<bits/stdc++.h>
using namespace std;
int a[101][101],f[101],t[101]; //a数组表示矩阵,f数组标记是否找过,t数组表示通过几个人 
int n,x,y;  //n表示共有多少人,x表示开始,y表示结束 
queue<int>bh; //定义队列 bh 
int bfs(int x) //从x节点开始搜索 
{   
    bh.push(x);  //x节点入队列 
    t[x]=0; f[x]=1;  //一开始通过0个人认识,把x节点标记为找过 
    while(bh.empty()!=1)  //如果队列非空 
    {   
        int i=bh.front();  //队首元素为i 
        if(i==y){ return t[i]-1;}  //如果i==y表示找到了,这个时候即通过了 t[i]-1个人 
        for(int j=1;j<=n;j++) //如果没有找到,看看这个人认识那些人 
        {   
            if(a[i][j]==1&&f[j]==0)  // a[i][j]==1表示认识并且这个人没找过 
            {  
                bh.push(j);      //把它认识的人放进队列 
                t[j]=t[i]+1;     //t的值加1 
                f[j]=1;        //这个人被标记成1 
            }
        }
        bh.pop();   //当前这个人已经搜索完了,出队列 
    }
}
int main()
{   
    int i,j;  
    cin>>n>>x>>y;
    for(i=1;i<=n;i++)
    {   
        for(j=1;j<=n;j++)
        {   
            cin>>a[i][j];
      }
    }
    cout<<bfs(x);  //调用bfs进行搜索 
}

标签:关系,表示,队列,认识,bh,网络,int,101
From: https://www.cnblogs.com/momotrace/p/guanxi_net.html

相关文章

  • 智安网络 |关于《等保合规,保障信息安全》
    随着信息化发展,网络安全面临越来越多的威胁与挑战,为了确保信息安全,各国政府纷纷制定安全法规和政策。中国政府实施等保工作可以说是中国信息安全保障的一项重要措施。为进一步完善安全保障机制,促进信息化和网络安全的发展,国家互联网信息办公室出台了“网络安全等级保护(以下简称等......
  • CS144 计算机网络 Lab2:TCP Receiver
    前言Lab1中我们使用双端队列实现了字节流重组器,可以将无序到达的数据重组为有序的字节流。Lab2将在此基础上实现TCPReceiver,在收到报文段之后将数据写入重组器中,并回复发送方。实验要求TCP接收方除了将收到的数据写入重组器中外,还需要告诉发送发送方:下一个需要的但是还......
  • 03.关系映射
    一、实体关系实体——数据实体,实体关系指的就是数据与数据之间的关系例如:用户和角色、房屋和楼栋、订单和商品实体关系分为以下四种:一对一关联实例:学生和校园卡、人和身份证、用户基本信息和详情数据表关系:主键关联(用户表主键和详情主键相同时,表示是匹配的数据)学生......
  • traceroute命令:网络诊断工具,它可以用于确定数据包从源主机到目标主机所需经过的路由器
    traceroute命令是一种网络诊断工具,它可以用于确定数据包从源主机到目标主机所需经过的路由器节点。traceroute通过发送UDP数据包或ICMPECHO请求,在数据包中设置递增的TTL(TimeToLive)值,每个TTL值代表距离源主机越来越远的路由器。当路由器收到TTL值为0的数据包时,将抛弃该数据包并......
  • 处理网络难题,还得靠这份网工经验合集
    网络维护,是很多初阶网工必须要做的工作。但说起来容易,做起来难,想要做好这个工作,需要的不仅仅是技术的加持,更多的是经验的积累。今天,和你分享一份关于一些网络维护过程中一些典型、经典问题的解决方法,希望能对你的工作有所帮助。典型问题①用户抱怨:整个网络变慢网络症状:影响所有连接......
  • 混合云网络打通
    概述多云管理集群分为两类,主集群和子集群。各个集群需要打通实现一个集群的pod能够访问到另一个集群的pod。这样才能实现应用的跨云部署。主机群一般会提供一些公共服务,子集群的pod一般会去使用,这样就需要实现主子集群的网络互通。实现方式就是端口固定,通过LB暴露,然后绑定域名,通......
  • 关于如何清空存在依赖关系的表
    设表student,course,scstudent中的sno为主键course中cno为主键sc中sno和cno为外键 如果按照student,course,sc的顺序情况,那么会出现因为student,course存在依赖关系而无法情况数据的情况因此这种情况下应该将顺序调整为sc,student,course这样就可以啦......
  • Mesh网络
    Mesh网络即”无线网格网络”,是“多跳(multi-hop)”网络,是由adhoc网络发展而来,是解决“最后一公里”问题的关键技术之一。在向下一代网络演进的过程中,无线是一个不可缺的技术。无线mesh可以与其它网络协同通信,是一个动态的可以不断扩展的网络架构无线Mesh网络是一种新无线局域网类......
  • TStack_独立网络节点硬件更换指南
    目录问题背景操作范围适用版本影响范围操作时段操作步骤1.查找所有位于该节点的主路由ID2.切换所有主路由到其它网络节点3.路由切换验证4.关闭网络服务5.关机6.硬件更换7.开机并检查服务问题背景由于服务器硬件问题,需要对该独立的网络节点进行关机更换硬件操作,该网络节......
  • 计算机网络详解——HTTP/1.1 优缺点
    一、优点1.1可扩展正是因为HTTP规范中限制很少,告诉你可以做什么,但是不会告诉你各种条条框框不能做什么,所以,很容易扩展,这也是为什么从HTTP/0.9诞生,一直扩展升级,添加更多的特性的原因。1.2传输可靠性由于底层是基于TCP协议的,所以继承了TCP传输数据的可靠性,主要体现在[1]:数据......