P2860 [USACO06JAN] Redundant Paths G

~~~~~      P2860 [USACO06JAN] Redundant Paths G ~~~~~      总题单链接

思路

~~~~~      我们发现在同一个边双连通分量中的点两两之间多有至少两条路，所以先缩点。

~~~~~      缩点后我们将度为 $1$ 的点两两配对即可。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;ll head[5005],egt=1;
struct Edge{ll v,nxt;
}eg[10005];
void add(ll u,ll v){eg[++egt]={v,head[u]};head[u]=egt;
}ll stk[5005],top,cnt;
ll n,m,scc[5005],du[5005];
ll dfn[5005],low[5005],tot;void Tarjan(ll p,ll ins){stk[++top]=p;dfn[p]=low[p]=++tot;for(ll i=head[p];i;i=eg[i].nxt){ll v=eg[i].v;if(!dfn[v]){Tarjan(v,i);low[p]=min(low[p],low[v]);if(low[v]>dfn[p]){cnt++;while(1){ll z=stk[top--];scc[z]=cnt;if(z==v)break;}}}else if(ins!=(i^1))low[p]=min(low[p],dfn[v]);}
}signed main(){ios::sync_with_stdio(false);cin>>n>>m;while(m--){ll x,y;cin>>x>>y;add(x,y);add(y,x);}for(ll i=1;i<=n;i++){if(!dfn[i]){Tarjan(i,0);if(top){cnt++;while(top)scc[stk[top--]]=cnt;}}}if(cnt==1){cout<<0;return 0;}for(ll u=1;u<=n;u++)for(ll i=head[u];i;i=eg[i].nxt){ll v=eg[i].v;if(scc[u]!=scc[v])du[scc[u]]++,du[scc[v]]++;}ll ans=0;for(ll i=1;i<=cnt;i++)if(du[i]==2)ans++;cout<<ans/2+ans%2;return 0;
}