Posted on 2010-08-08 19:42
Uriel 阅读(212)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
搜索 、
图论
求割点没什么问题，但是求去掉这个割点图被分为几个连通分支没什么思路，看了解题报告恍然大悟，DFS就行了啊~~
枚举点，去掉看暴力DFS看被分成几块，判了是否是割点的同时也知道了连通分支数
//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;
}