Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
发个AC 0ms代码#include<iostream> #include<cstring> #include<cstdio> using namespace std; int dfn[105],low[105],prt[105],g[105][105]; int n,cnt,ans,son,vis[105]; void init() { int i,j; char ch; cnt=0,ans=0;son=0; memset(prt,0,sizeof(prt)); memset(g,0,sizeof(g)); memset(dfn,0,sizeof(dfn)); memset(vis,0,sizeof(vis)); while(scanf("%d",&i)&&i!=0) { while(1) { scanf("%d%c",&j,&ch); g[i][j]=1;g[j][i]=1; if(ch=='\n')break; } } } void dfs(int u) { int i; low[u]=dfn[u]=++cnt; for(int i=1;i<=n;i++) if(g[u][i]&&prt[u]!=i) { if(!dfn[i]) { prt[i]=u; dfs(i); low[u]=min(low[u],low[i]); if(low[i]>=dfn[u]) { if(!vis[u]){ans++;vis[u]=1;} if(u==1)son++; } } else low[u]=min(low[u],dfn[i]); } } int main() { while(scanf("%d",&n)) { if(n==0)break; init(); dfs(1); if(son==1)ans--; printf("%d\n",ans); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator