还不会双连通分量的朋友，请扣->这里<-
No response.
在一个边双连通分量里面，所有的结点的low[ ]都是一样的哟。 所以可以缩点哟。 缩完点以后一定要证明哟。
//#include <bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstring> #include<stack> #include<set> #include<map> #include<queue> #include<math.h> #include<algorithm> typedef long long LL; using namespace std; //#pragma comment(linker, "/STACK:102400000,102400000") const int INF=0x3f3f3f3f; const int N=5e3+10; struct Edge { int to; int next; bool cut; } edge[N*4]; int tol,head[N],n,m; void init() { tol=0; memset(head,-1,sizeof(head)); } void add(int u,int v) { edge[tol].to=v; edge[tol].next=head[u]; head[u]=tol++; } int low[N],dfn[N]; int ind; void Tarjan(int u,int pre) { int v; low[u]=dfn[u]=ind++; for(int i=head[u]; ~i; i=edge[i].next) { v=edge[i].to; if((i^1)==pre) continue; if(!dfn[v]){ Tarjan(v,i); low[u]=min(low[u],low[v]); } else low[u]=min(low[u],dfn[v]); } } int deg[N]; void solve() { memset(deg,0,sizeof(deg)); memset(dfn,0,sizeof(dfn)); ind=1; Tarjan(1,-1); for(int i=1;i<=n;i++) { for(int k=head[i];~k;k=edge[k].next) { int v=edge[k].to; if(low[v] != low[i]) deg[low[i]]++; } } int res=0; for(int i=1;i<=n;i++) if(deg[i]==1) res++; printf("%d\n",(res+1)/2); } int main() { int u,v; scanf("%d%d",&n,&m); init(); while(m--){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } solve(); return 0; }