POJ 3177

 1 include <iostream>
 2 #include <cstdio>
 3 #include <string.h>
 4 using namespace std;
 5 const int N=10002;
 6 int dfn[N],low[N],first[N],in[N];
 7 bool visit[N];
 8 int mun,deep,sum,n;
 9 struct edge{
10     int v,next;
11 }e[N];
12 void init(){
13     mun=0;
14     deep=0;
15     sum=0;
16     memset(first,-1,sizeof(first));
17     memset(dfn,0,sizeof(dfn));
18     memset(low,0,sizeof(low));
19     memset(in,0,sizeof(in));
20 }
21 void addedge(int u,int v){
22     e[mun].v=v;
23     e[mun].next=first[u];
24     first[u]=mun++;
25 }
26 void dfs(int u,int fa){
27     dfn[u]=low[u]=++deep;
28     for(int i=first[u];i!=-1;i=e[i].next){
29         int v=e[i].v;
30         if(!dfn[v]){
31             dfs(v,u);
32             low[u]=min(low[v],low[u]);
33         }
34         else if(v!=fa)low[u]=min(low[u],dfn[v]);
35     }
36 }
37 void count(){
38     for(int i = 1;i <=n;i ++){
39         memset(visit,0,sizeof(visit));                                  //visit是为了防止重边
40         for(int j=first[i];j!=-1;j=e[j].next){
41             int v=e[j].v;
42             if (low[v]!= low[i]&&!visit[v]){in[low[i]]++;visit[v]=1;}
43         }
44     }
45     for (int i = 1;i <= n;i ++)                                         //统计度为1的边数
46         if (in[i] == 1) sum ++;
47 }
48 int main(){
49     int x,y,m;
50     while(scanf("%d%d",&n,&m)!=EOF){
51         init();
52         while(m--){
53             scanf("%d%d",&x,&y);                                        //边为双向；
54             addedge(x,y);
55             addedge(y,x);
56         }
57         dfs(1,-1);
58         count();
59         printf ("%d\n",(sum + 1)/2);
60     }
61     return 0;
62 }