这题真是没什么好说的。。。赤裸裸的求割点直接模板上
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<vector> 5 #define maxn 1100 6 7 using namespace std; 8 9 vector<int> g[maxn]; 10 int dfn[maxn],low[maxn]; 11 int vis[maxn],cnt[maxn]; 12 int k=1,f=0,index=0,m; 13 void dfs(int x) 14 { 15 // cout<<"1"<<endl; 16 int c=0; 17 for(int i=0;i<g[x].size();i++) 18 { 19 int e=g[x][i]; 20 if(vis[e]==0) 21 { 22 dfn[e]=low[e]=++index; 23 vis[e]=1; 24 dfs(e); 25 low[x]=min(low[e],low[x]); 26 if(low[e]>=dfn[x]) 27 { 28 cnt[x]++; 29 } 30 } 31 else low[x]=min(low[x],dfn[e]); 32 } 33 } 34 void solve() 35 { 36 f=index=0; 37 memset(dfn,0,sizeof(dfn)); 38 memset(cnt,0,sizeof(cnt)); 39 memset(vis,0,sizeof(vis)); 40 memset(low,0,sizeof(low)); 41 printf("Network #%d ",k++); 42 vis[1]=1; 43 dfn[1]=low[1]=++index; 44 dfs(1); 45 if(cnt[1]>=1) cnt[1]--; 46 for(int i=1;i<=m;i++) 47 { 48 if(cnt[i]) 49 { 50 printf(" SPF node %d leaves %d subnets ",i,cnt[i]+1); 51 f=1; 52 } 53 } 54 if(f==0) printf(" No SPF nodes "); 55 printf(" "); 56 } 57 int main() 58 { 59 int a,b; 60 while(scanf("%d",&a)!=EOF) 61 { 62 for(int i=1;i<=maxn;i++) 63 g[i].clear(); 64 if(a==0) break; 65 scanf("%d",&b); 66 g[a].push_back(b); 67 g[b].push_back(a); 68 m=a<b?b:a; 69 while(1) 70 { 71 int x,y; 72 scanf("%d",&x); 73 if(x==0) break; 74 scanf("%d",&y); 75 g[x].push_back(y); 76 g[y].push_back(x); 77 m=m>x?m:x; 78 m=m>y?m:y; 79 } 80 solve(); 81 } 82 return 0; 83 }