ACM 315 Network
題目說明:(因為我國文有點差 光是讀懂就搞了很久 幫同類解釋一下)
換個方式說:如果這個機房的電停掉的話 除了這個點以外 其他的機房都可以藉由別的電場提供電而亮 若有不是這個機房而不亮的話 那麼這個機房就是個critical的機房
作法:BFS(連結)
因為我不會用內建的分析字串 暴力囉!!
1.假設那一點是的話 將那一點產生的節點斷掉
2.隨便設一個點當做起點
3.由這個起點若能走到除了假設的那一點之外的所有點
4.如果沒辦法的話 就是ANS++;
5.持續上面的作法 假設所有點都是 再去做判斷!
2009/7/17 更新為相鄰矩陣的寫法 速度*4(第2程式碼)
/*********************************************************/
#include<stdio.h>#include<stdlib.h>
#include<string.h>
main()
{
int n;
char x[1000];
while(scanf("%d",&n)==1&&n!=0)
{
scanf(" ");
char map[101][101]={0},a,b,c,d;
while(gets(x))
{
int m=strlen(x),temp=0,temp1=0;
for(a=0;a<m;a++)
if(x[a]!=' ') temp=temp*10+x[a]-48;
else break;
if(temp==0) break;
a++;
for(;a<m;a++)
if(x[a]<=57&&x[a]>=48)
temp1=temp1*10+x[a]-48;
else {map[temp][temp1]=1;map[temp1][temp]=1;temp1=0;}
map[temp][temp1]=1;map[temp1][temp]=1;
}
int ans=0;
for(a=1;a<=n;a++)
{
int find=0;
for(b=1;b<=n;b++) /*將它們的連結刪除*/
if(map[a][b]==1) map[b][a]=0;
int flag[101]={0};/*這個數字是否有出現過*/
int queue[100]={0},top=0,start;
for(b=1;b<=n;b++)
{
if(a==b) continue;
else {start=b;break;} /*起點*/
}
queue[0]=start; /*必須從任起點 都能到任何地方 才不算是*/
flag[start]=1;
for(b=0;b<=top;b++) /*BFS*/
{
int nn=queue[b];
for(c=1;c<=n;c++)
if(map[nn][c]==1&&flag[c]==0) {top++;queue[top]=c;flag[c]=1;}
}
for(b=1;b<=n;b++)
if(flag[b]==1) {find++;}
for(b=1;b<=n;b++) /*將它們之間的連結還原*/
if(map[a][b]==1) map[b][a]=1;
if(find!=n-1) ans++;
}
printf("%d\n",ans);
}
return 0;
}
/***************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
main()
{
int n;
char x[1000];
while(scanf("%d",&n)==1&&n!=0)
{
scanf(" ");
char map[101][101]={0},a,b,c,d;
int maptop[101]={0};
while(gets(x))
{
int m=strlen(x),temp=0,temp1=0;
for(a=0;a<m;a++)
if(x[a]!=' ') temp=temp*10+x[a]-48;
else break;
if(temp==0) break;
a++;
for(;a<m;a++)
if(x[a]<=57&&x[a]>=48)
temp1=temp1*10+x[a]-48;
else
{
map[temp][maptop[temp]]=temp1;
maptop[temp]++;
map[temp1][maptop[temp1]]=temp;
maptop[temp1]++;
temp1=0;
}
map[temp][maptop[temp]]=temp1;
maptop[temp]++;
map[temp1][maptop[temp1]]=temp;
maptop[temp1]++;
}
int ans=0;
/* for(a=1;a<=n;a++)
{
for(b=0;b<=n;b++)
printf("%d ",map[a][b]);
printf("\n");
}*/
for(a=1;a<=n;a++)
{
int find=0;
int flag[101]={0};/*這個數字是否有出現過*/
int queue[100]={0},top=0,start;
if(a==1) start=2;
else start=1;
queue[0]=start; /*必須從任起點 都能到任何地方 才不算是*/
flag[start]=1;
for(b=0;b<=top;b++) /*BFS*/
{
int nn=queue[b];
for(c=0;c<maptop[nn];c++)
if(map[nn][c]!=a&&flag[map[nn][c]]==0) {top++;queue[top]=map[nn][c];flag[map[nn][c]]=1;}
}
for(b=1;b<=n;b++)
if(flag[b]!=1&&b!=a) break;
if(b!=n+1) ans++;
}
printf("%d\n",ans);
}
return 0;
}