#include <cstdio>
#include <vector>
#include <deque>
using namespace std;
#define MAXN 5010
vector<int> map[MAXN];
deque<int> stack;
int v, e, cnt, cnt0;
int low[MAXN], ID[MAXN];
void dfs( int w, int parent )
{
low[w]= cnt++; stack.push_front(w);
int min= low[w];
for( size_t i= 0; i< map[w].size(); ++i )
{
int v= map[w][i];
if( low[v]== 0 )
{
dfs( v, w );
if( low[v]< min ) min= low[v];
}
else if( v!= parent && low[v]< min ) min= low[v];
}
if( low[w]> min ) { low[w]= min; return; }
while( stack.front()!= w )
{
ID[ stack.front() ]= cnt0;
stack.pop_front();
}
ID[w]= cnt0; stack.pop_front();
cnt0++;
}
bool isok( int u, int v )
{
for( size_t i= 0; i< map[u].size(); ++i )
if( map[u][i]== v ) return false;
return true;
}
int main()
{
while( scanf("%d%d",&v,&e)!= EOF )
{
for( int i= 0; i<= v; ++i )
map[i].clear();
stack.clear();
memset( low, 0, sizeof(low) );
memset( ID, 0, sizeof(ID) );
cnt= 1; cnt0= 1;
int a, b;
for( int i= 0; i< e; ++i )
{
scanf("%d%d",&a,&b);
if( isok(a,b) )
{
map[a].push_back(b);
map[b].push_back(a);
}
}
int degree[MAXN];
memset( degree, 0, sizeof(degree) );
dfs( 1, 0 );
int re= 0;
for( int i= 1; i<= v; ++i )
for( size_t j= 0; j< map[i].size(); ++j )
if( ID[i]!= ID[ map[i][j] ] ) degree[ ID[i] ]++;
for( int i= 1; i<= v; ++i )
if( degree[i]== 1 ) re++;
printf("%d\n", (re+ 1)/ 2 );
}
return 0;
}
posted on 2009-02-25 17:05
Darren 閱讀(325)
評論(0) 編輯 收藏 引用