首页 > 代码库 > NYOJ 641 摧毁网络
NYOJ 641 摧毁网络
摧毁网络
时间限制:1000 ms | 内存限制:65535 KB
难度:2
- 描述
告诉你一个惊天的秘密,其实吧,小蜗牛是一个高级特工。他拥有特工的应该有所有本领。现在他来到了一个小镇,他的任务就是要切断一个恐怖组织的整个通信网络。但是恐怖分子没有想象中的那么白痴,恐怖分子把自己的网络混杂在了民用的网络中,现在小蜗牛必须弄清楚到底有多少的网络,才可以采取必要的行动。从组织那他拿到了小镇的网络分布地图,每户居民都有固定的编号。
- 输入
- 输入有多组。
每组数据的第一行都给一个N(0<=N<=1000)表示有N户居民,给一个M代表有M条线路。接下来的M行每行都给两个数,代表线路连通的两户居民编号。可能一户居民跟多户居民都有连通的线路。 - 输出
- 对于每组样例,输出有小镇多少个网络。
- 样例输入
4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5
- 样例输出
2 1 3
我用的深搜!可是时间和空间耗费都非常大!
AC码:
#include<stdio.h> #include<string.h> int G[1001][1001],visit[1001]; int n; void DFS(int x) { int i; visit[x]=1; for(i=1;i<=n;i++) { if(!visit[i]&&G[x][i]&&(i!=x)) { DFS(i); } } } int main() { int m,i,count,a,b; while(~scanf("%d%d",&n,&m)) { memset(G,0,sizeof(G)); memset(visit,0,sizeof(visit)); for(i=0;i<m;i++) { scanf("%d%d",&a,&b); G[a][b]=G[b][a]=1; } count=0; for(i=1;i<=n;i++) { if(!visit[i]) { DFS(i); count++; } } printf("%d\n",count); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。