九度OJ 1109：连通图 （最小生成树）
2024-09-08 05:14:34
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：2783
解决：1432
- 题目描述：
-
给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。
- 输入：
-
每组数据的第一行是两个整数 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
思路：
最基本的最小生成树。
代码：
#include <stdio.h>
#include <string.h>
#define N 1000
int id[N+1];
int n;
int count;
void init()
{
for (int i=1; i<=n; i++)
id[i] = i;
count = n;
}
void combine(int a, int b)
{
if (id[a] == id[b])
return ;
else
{
int tmp = id[b];
for (int i=1; i<=n; i++)
{
if (id[i] == tmp)
id[i] = id[a];
}
count --;
}
}
int main(void)
{
int m;
int i;
int a, b;
while (scanf("%d%d", &n, &m) != EOF && n)
{
init();
for (i=0; i<m; i++)
{
scanf("%d%d", &a, &b);
combine(a, b);
}
if (count == 1)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
/**************************************************************
Problem: 1109
User: liangrx06
Language: C
Result: Accepted
Time:30 ms
Memory:916 kb
****************************************************************/
最新文章
- 如何自动化一键部署PHP项目
- 斗地主——扎金花——3DMark
- [DBW]一个小巧的Class方案
- 几张图弄明白ios布局中的尺寸问题
- js 页面值变动监听
- eclipse中安装svn插件
- 65.OV7725图像倒置180度
- c语言输入与输出库函数#include<stdio.h>
- Calender设置固定时间遇到的问题
- Android fragment切换后onresume时报 Attempt to write to field 'int android.support.v4.app.Fragment.mNextAnim'
- git配置代理
- 20165223《JAVA程序设计》第二周学习总结
- Confluence 6 找到在创建 XML 备份的时候出现的错误
- django 数据库查询的几个知识点
- （18）模型层 -ORM之msql 多表操作（字段的属性）
- 对怎样充分利用安卓官方开发网站的一个简单性介绍介绍-https://developer.android.google.cn/docs/
- Linux中MySQL中文乱码问题
- MVP 模式简单易懂的介绍方式
- Struts1简单开发流程梳理
- Google Congestion Control介绍