记录编号	143026	评测结果	AAAAAAAAAAAAAAAAA
题目名称	[USACO Jan06]Redundant Paths	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2014-12-12 16:42:16	内存使用	0.43 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x3fffffff;
//==============struct declaration=============
struct adj{
  int to,no;
  adj(int to=0,int no=0):to(to),no(no){}
};
//==============var declaration=================
const int MAXN=5010;
int n,m,Index=0;
vector <adj> Edge[MAXN];
int pre[MAXN],low[MAXN],deg[MAXN];
//==============function declaration============
void tarjan(int x,int pa);
//==============main code=======================
int main()
{  
#define FILE__
#ifdef FILE__
  freopen("rpathsa.in","r",stdin);
  freopen("rpathsa.out","w",stdout);
#endif  
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++){
    int s,e;
    scanf("%d%d",&s,&e);
    Edge[s].push_back(adj(e,i));
    Edge[e].push_back(adj(s,i));
  }
  memset(pre,0,sizeof(pre));memset(deg,0,sizeof(deg));
  tarjan(1,-1);
  for(int x=1;x<=n;x++){
    int siz=Edge[x].size();
    for(int i=0;i<siz;i++){
      int &e=Edge[x][i].to;
      if (low[e]==low[x]) continue;
      deg[low[e]]++;
    }
  }
  int ans=0;
  for(int i=1;i<=n;i++){
    if (deg[i]==1)
      ans++;
  }
  printf("%d\n",(ans+1)/2);
  return 0;
}
//================fuction code====================
void tarjan(int x,int pa)
{
  pre[x]=low[x]=++Index;
  int siz=Edge[x].size();
  for(int i=0;i<siz;i++){
    adj &e=Edge[x][i];
    if (e.no==pa) continue;
    if (pre[e.to]!=0)
      low[x]=min(low[x],pre[e.to]);
    else{
      tarjan(e.to,e.no);
      low[x]=min(low[x],low[e.to]);
    }
  }
}