poj3352
#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int maxn=1000+10; int n,m; vector<int> G[maxn]; int dfs_clock; int pre[maxn],low[maxn]; int degree[maxn]; int tarjan(int u,int fa) { int lowu=pre[u]=++dfs_clock; for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(v==fa) continue; if(!pre[v]) { int lowv=tarjan(v,u); lowu=min(lowu,lowv); } else if(pre[v]<pre[u]) lowu=min(lowu,pre[v]); } return low[u]=lowu; } int main() { scanf("%d%d",&n,&m); dfs_clock=0; memset(pre,0,sizeof(pre)); memset(degree,0,sizeof(degree)); for(int i=1;i<=n;i++) G[i].clear(); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } tarjan(1,-1);//得出所有节点的low值,每个不同的low值代表一个边双连通分量 for(int u=1;u<=n;u++)//遍历每条边 for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(low[u]!=low[v]) degree[low[v]]++; } int cnt=0; for(int i=1;i<=n;i++)if(degree[i]==1) cnt++; printf("%d\n",(cnt+1)/2 ); }