<题目链接>
题目描述:
月月和华华一起去逛公园了。公园很大,为了方便,可以抽象的看成一个N个点M条边的无向连通图(点是景点,边是道路)。公园唯一的入口在1号点,月月和华华要从这里出发,并打算参观所有的景点。因为他们感情很好,走多远都不会觉得无聊,所以所有景点和道路都可以无数次的重复经过。月月发现,有些路可走可不走,有些路则必须要走,否则就无法参观所有的景点。现在月月想知道,有几条路是不一定要经过的。因为这是个很正常的公园,所以没有重边和自环。$(1 \leq N\leq10^5,1 \leq M\leq3*10^5)$
输入描述:
第一行两个正整数N和M,表示点数和边数。
接下来M行,每行两个正整数U和V表示一条无向边。
保证给定的图是连通的。
输出描述:
输出一行一个非负整数表示不一定要经过的边有几条。输入:
5 5 1 2 2 3 3 4 4 5 3 5 输出:
3 说明: 例如第三条边,月月和华华可以依次走过第一条、第二条、第五条、第四条边走过全部的景点,所以第三条边不一定要经过。同理还有第四条、第五条边,答案为3。 解题分析:
该无向图的那些割边是一定要经过的,否则不能经过所有的点,而那些非割边,就是不必要的。所以本题就是无向图求桥的模板题。
#include <bits/stdc++.h> using namespace std; , M = 3e5+; ]; int head[N],dfn[N],low[N]; ,tot; ]; inline void add(int u,int v){ e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt; } void Tarjan(int u,int id){ dfn[u]=low[u]=++tot; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(!dfn[v]){ Tarjan(v,i); low[u]=min(low[u],low[v]); ]=; //将割边标记 }))low[u]=min(low[u],dfn[v]); //i为非搜索树上的边,才能用来更新low值 } } int main(){ scanf("%d%d",&n,&m); ;i<=m;i++){ int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u); } Tarjan(,); //因为该无向图图保证连通,所以只用跑一个点就行 ; ;i<cnt;i+=)if(bridge[i])++ans; printf("%d\n",m-ans); }