首页 > 代码库 > 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;
}