JOBDU 1109 连通图
2024-08-25 00:03:09
题目1109:连通图
时间限制:1 秒
内存限制:32 兆
特殊判题:否
提交:4192
解决:2224
- 题目描述:
-
给定一个无向图和其中的所有边,判断这个图是否所有顶点都是连通的。
- 输入:
-
每组数据的第一行是两个整数 n 和 m(0<=n<=1000)。n 表示图的顶点数目,m 表示图中边的数目。如果 n 为 0 表示输入结束。随后有 m 行数据,每行有两个值 x 和 y(0<x, y <=n),表示顶点 x 和 y 相连,顶点的编号从 1 开始计算。输入不保证这些边是否重复。
- 输出:
-
对于每组输入数据,如果所有顶点都是连通的,输出"YES",否则输出"NO"。
- 样例输入:
-
4 3
1 2
2 3
3 2
3 2
1 2
2 3
0 0
- 样例输出:
-
NO
YES
- 来源:
- 2011年吉林大学计算机研究生机试真题
- 用DFS判断是否连通,判断图是否连通一般用DFS把,,,个人感觉
-
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<map>
using namespace std;
#define INF 65537
#define maxn 1010
int mapn[maxn][maxn],visited[maxn];
void DFS(int i,int n)
{
visited[i]=;
for(int j=;j<=n;j++)
if(mapn[i][j]==&&visited[j]==)
DFS(j,n);
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
if(n==)
break;
memset(visited,,sizeof(visited));
memset(mapn,,sizeof(mapn));
while(m--)
{
int a,b;
cin >> a >> b;
mapn[a][b]=;
mapn[b][a]=;
}
DFS(,n);
int flag=;
for(int i=;i<=n;i++)
if(visited[i]==)
flag=;
if(flag)
cout << "YES" << endl;
else cout << "NO" << endl;
}
return ;
}
最新文章
- C++中的文件读取结束
- iOS:访问地址薄
- js运动 缓冲运动
- 大四实习准备1_java构造器_android ListView
- jmeter中webdriver插件,进行自动化压测
- 最完整的合并相交集合的Java代码(查并集)
- Sql语句 不支持中文 国外数据库
- 为什么ELF文件的加载地址是0x8048000
- windows bat命令编写大全
- javascript-Blob文件对象
- 【IPC进程间通信之四】数据复制消息WM_COPYDATA
- DBCP数据源的使用
- C# 基于Bootstrap的三级联动
- Concat
- react 脚手架 立即可以写业务 react + react-router-dom + less + axios + antd
- Django Class Based View
- Java集合框架——jdk 1.8 ArrayList 源码解析
- BZOJ.1758.[WC2010]重建计划(分数规划 点分治 单调队列/长链剖分 线段树)
- map set iterator not incrementable 解决办法
- 不用webservice wcf提供服务,用Rest更轻量