摧毀網(wǎng)絡(luò)

時(shí)間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：2 描述

告訴你一個(gè)驚天的秘密，其實(shí)吧，小蝸牛是一個(gè)高級特工。他擁有特工的應(yīng)該有所有本領(lǐng)。現(xiàn)在他來到了一個(gè)小鎮(zhèn)，他的任務(wù)就是要切斷一個(gè)恐怖組織的整個(gè)通信網(wǎng)絡(luò)。但是恐怖分子沒有想象中的那么白癡，恐怖分子把自己的網(wǎng)絡(luò)混雜在了民用的網(wǎng)絡(luò)中，現(xiàn)在小蝸牛必須弄清楚到底有多少的網(wǎng)絡(luò)，才可以采取必要的行動。從組織那他拿到了小鎮(zhèn)的網(wǎng)絡(luò)分布地圖，每戶居民都有固定的編號。

輸入

輸入有多組。
每組數(shù)據(jù)的第一行都給一個(gè)N（0<=N<=1000）表示有N戶居民，給一個(gè)M代表有M條線路。接下來的M行每行都給兩個(gè)數(shù)，代表線路連通的兩戶居民編號。可能一戶居民跟多戶居民都有連通的線路。

輸出

對于每組樣例，輸出有小鎮(zhèn)多少個(gè)網(wǎng)絡(luò)。

樣例輸入

4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5

樣例輸出

2 1 3

我用的深搜！可是時(shí)間和空間耗費(fèi)都非常大！

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; }

總結(jié)

以上是生活随笔為你收集整理的NYOJ 641 摧毁网络的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。