解题思路
刚开始是找的桥,后来发现这样不对,因为一条链就可以被卡。后来想到应该缩点后找到度数为1 的点然后两两配对。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> using namespace std; const int MAXN = 5005; const int MAXM = 10005; inline int rd(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {f=ch==‘-‘?0:1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();} return f?x:-x; } int n,m,head[MAXN],cnt,to[MAXM<<1],nxt[MAXM<<1],num,du[MAXN]; int dfn[MAXN],low[MAXN],ans,col[MAXN],col_num,stk[MAXN],top; bool vis[MAXN]; set<pair<int,int> > S; inline void add(int bg,int ed){ to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt; } void tarjan(int x,int fa){ dfn[x]=low[x]=++num;vis[x]=1;stk[++top]=x;int u; for(register int i=head[x];i;i=nxt[i]){ u=to[i];if(u==fa) continue; if(!dfn[u]) {tarjan(u,x);low[x]=min(low[x],low[u]);} else if(vis[x])low[x]=min(low[x],dfn[u]); } if(low[x]!=dfn[x]) return; col[x]=++col_num;vis[x]=0; while(stk[top]!=x) { col[stk[top]]=col_num; vis[stk[top--]]=0; }top--; } int main(){ n=rd(),m=rd();int x,y;pair<int,int> p; for(int i=1;i<=m;i++){ x=rd(),y=rd();p=make_pair(x,y); if(S.find(p)!=S.end()) continue; S.insert(p);S.insert(make_pair(y,x)); add(x,y),add(y,x); } tarjan(1,1); // for(int i=1;i<=n;i++) cout<<col[i]<<" "; for(int i=1;i<=n;i++) for(int j=head[i];j;j=nxt[j]) if(col[i]!=col[to[j]]) du[col[i]]++,du[col[to[j]]]++; for(int i=1;i<=col_num;i++) if(du[i]==2) ans++; cout<<(ans+1)/2; return 0; }