思路：
dfs求出所有点的low值，然后对每个连通分量进行缩点，可以通过low来进行缩点。虽然在同一连通分量里可能存在不同的low值，但这并不影响缩点。将每个连通分量缩为一个点后，只要求出这个缩点后的树上的叶子节点个数就行了。结果为(leaf+1)/2。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<map> #define Maxn 1010 #define Maxm Maxn*10 using namespace std; int index[Maxn],degree[Maxn],dfn[Maxn],low[Maxn],e,n,lab=0,num,visit[Maxn][Maxn]; void init() { memset(index,-1,sizeof(index)); memset(degree,0,sizeof(degree)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(visit,0,sizeof(visit)); e=lab=num=0; } struct Edge{ int from,to,next,v; }edge[Maxm]; void addedge(int from, int to) { edge[e].v=0; edge[e].from=from; edge[e].to=to; edge[e].next=index[from]; index[from]=e++; edge[e].v=0; edge[e].to=from; edge[e].from=to; edge[e].next=index[to]; index[to]=e++; } int dfs(int u) { dfn[u]=low[u]=++lab; int i,j,temp; for(i=index[u];i!=-1;i=edge[i].next) { temp=edge[i].to; if(edge[i].v) continue; edge[i].v=edge[i^1].v=1; if(!dfn[temp]) { dfs(temp); low[u]=min(low[u],low[temp]); } low[u]=min(low[u],dfn[temp]); } return 0; } int solve() { int i,j,temp; for(i=1;i<=n;i++) { for(j=index[i];j!=-1;j=edge[j].next) { int temp=edge[j].to; if(low[i]!=low[temp]) { degree[low[i]]++; } } } return 0; } int main() { int m,i,j,a,b; while(scanf("%d%d",&n,&m)!=EOF) { init(); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); if(!visit[a][b]) { addedge(a,b); visit[a][b]=visit[b][a]=1; } } int ans=0; dfs(1); solve(); for(i=1;i<=n;i++) if(degree[i]==1) ans++; printf("%d ",(ans+1)/2); } return 0; }