思路与poj3177一模一样。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define Maxn 1010 #define Maxm Maxn*Maxn #define inf 0x7fffffff using namespace std; int dfn[Maxn],low[Maxn],degree[Maxn],e,n,lab,index[Maxn]; struct Edge{ int to,from,next,v; }edge[Maxm]; void init() { memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(degree,0,sizeof(degree)); memset(index,-1,sizeof(index)); e=lab=0; } void addedge(int from, int to) { edge[e].v=0; edge[e].from=from; edge[e].to=to; edge[e].next=index[from]; index[from]=e++; edge[e].v=0; edge[e].from=to; edge[e].to=from; edge[e].next=index[to]; index[to]=e++; } void dfs(int u) { dfn[u]=low[u]=++lab; int i,j,temp; for(i=index[u];i!=-1;i=edge[i].next) { temp=edge[i].to; if(edge[i].v) continue; edge[i].v=edge[i^1].v=1; if(!dfn[temp]) { dfs(temp); low[u]=min(low[u],low[temp]); } low[u]=min(low[u],dfn[temp]); } } int solve() { int i,j,temp=0; for(i=1;i<=n;i++) { for(j=index[i];j!=-1;j=edge[j].next) { if(low[i]!=low[edge[j].to]) degree[low[i]]++; } } for(i=1;i<=n;i++) if(degree[i]==1) temp++; return (temp+1)/2; } int main() { int m,i,j,a,b; while(scanf("%d%d",&n,&m)!=EOF) { init(); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); addedge(a,b); } dfs(1); printf("%d ",solve()); } return 0; }