POJ--3352 道路建设

10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10

#include<iostream>
using namespace std;
const int maxn = 1000+10;
int head[maxn],num,vis[maxn],dfn[maxn],low[maxn],cnt,degree[maxn],leaf;//num:用于edge下标的控制 ,cnt:用于dfn的标号 
struct Edge{
  int next,to;
}e[maxn * maxn];
void add(int u,int v){
  e[++num].next = head[u];
  e[num].to = v;
  head[u] = num;
}
void tanjar(int u,int fa){
  dfn[u] = low[u] = ++cnt;
  for(int i = head[u]; i; i = e[i].next){
    int v = e[i].to;
    if(v==fa){
      continue;
    }
    if(!dfn[v]){
      tanjar(v,u);
      low[u] = min(low[u],low[v]);
    }else{
      low[u] = min(low[u],low[v]);
    }
  }
}
int main()
{
  int n,m,u,v;
  cin>>n>>m;
  while(m--){
    cin>>u>>v;
    add(u,v);
    add(v,u);
  }
  tanjar(1,0);
  for(int u = 1; u <= n; u++){//缩点 
    for(int j = head[u]; j; j =e[j].next ){
      int v = e[j].to;
      if(low[u]!=low[v]){
        degree[low[u]]++;
      }
    }
  }
  for(int i = 1;i <= n; i++){
    if(degree[i]==1){
      leaf++;
    }
  }
  cout<<(leaf+1)/2<<endl;
  return 0;
}