Posted on 2010-08-08 19:42
Uriel 閱讀(244)
評論(0) 編輯 收藏 引用 所屬分類:
POJ 、
搜索 、
圖論
求割點沒什么問題，但是求去掉這個割點圖被分為幾個連通分支沒什么思路，看了解題報告恍然大悟，DFS就行了啊~~
枚舉點，去掉看暴力DFS看被分成幾塊，判了是否是割點的同時也知道了連通分支數(shù)
//Problem: 1523 User: Uriel
//Memory: 4136K Time: 16MS
//Language: C++ Result: Accepted
//Version: DFS
//2010.08.07
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 1010
int num;
int map[N][N],arr[N];
bool vis[N];
int Loc(int k)
{
int i=0;
for(i=0;i<num;i++){
if(arr[i]==k)break;
}
if(i==num){
arr[num++]=k;
return num-1;
}
return i;
}
void DFS(int x){
vis[x]=true;
for(int j=0;j<num;j++){
if(!vis[j] && map[x][j])DFS(j);
}
}
int main(){
int g=1,x,y,a,b,l,s;
while(scanf("%d",&x),x){
scanf("%d",&y);
num=0;
a=Loc(x);b=Loc(y);
map[a][b]=map[b][a]=1;
while(scanf("%d",&x),x){
scanf("%d",&y);
a=Loc(x);b=Loc(y);
map[a][b]=map[b][a]=1;
}
printf("Network #%d\n",g++);
l=num-1;
for(int i=0;i<num;i++){
memset(vis,false,sizeof(vis));
s=0;
vis[i]=true;
for(int j=0;j<num;j++)
if(!vis[j]){
DFS(j);
s++;
}
if(s>1){
printf(" SPF node %d leaves %d subnets\n",arr[i],s);
}
else
l--;
}
if(l==-1)printf(" No SPF nodes\n");
printf("\n");
memset(map,0,sizeof(map));
}
return 0;
}