编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms-------------------------Accepted 有效得分：100 有效耗时：0ms 深搜+用栈存储节点！

第10个点死活超时，cheat过了

恩..cheat还是不好，处理一下算了

首先要理解好题目，两个点之间有两条完全不同的路的意思是这两个点在一个圈里面（顺时针走和逆时针走自然有两种）。

第一问：

显然图中会存在一些圈，而这些把圈与圈之间相连的边我们称之为桥（注意，桥不会是某个圈的一部分），如果图中圈与圈之间有相交，我们还是把它们看成一个圈，最后第一问的解就是图中有多少桥，也就是圈数-1。

找圈可以使用dfs遍历，一边维护一个栈，每遍历到一个点就压入，遍历完便弹出。设目前顶点k，如果k以前已经遍历到过，则说明存在圈，这时我们可以从栈顶向下找，把每个点都加入集合，直到k在栈中再次出现为止。那么怎么加入集合呢，我们可以使用并查集，把圈中每个结点的父结点都连到k的父结点上面去，因为使用了并查集，所以即使出现圈与圈相交的情况，也会把之前的圈也连到k上面。最后看看图中有多少个集合，便有多少个圈了。

第二问：

题目的意思显然是让我们把整个图都连成圈。因为在第一问的时候使用了并查集，可以说把一个圈看成了一个顶点，最后我们只要找到有多少度为1的顶点，图可以表示成如下（圈全部压缩为顶点）

......

/ / \ \

叶子 叶子 叶子 叶子

上面的...我们其实不用管它有多复杂，完全可以把它就看成是一个树根。

然后容易看出我们所需连的边就是（叶子数+1)div 2

......

/ / \ \

叶子-- 叶子 叶子-- 叶子

如图为叶子数=4时只需要2条边。

注意：题目中可能出现重边的情况，这时我们可以新加入一个顶点k，把重边变成,[k,j]。

1325.pas

无向图缩点，先求桥，除去桥就是环了

Flag 　　Accepted

题号 　　P1325

类型(?) 　　图结构

通过 　　11人

提交 　　141次

通过率 　　8%

难度 　　3

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

好"简单"的说...yours姐姐大牛风范珍藏版..

(ECHO 其实这题无敌简单,居然才7人)

实在无语 膜拜(抽RP)

不是，如果两个环中间只有一条路连接，也要添边的。怀疑要缩点，编编太麻烦就放弃了~

第二问不就是 CEOI2000 的那道新修公路么？ 把块找出来建树，然后答案就是

（叶子+1）/2 ？？ 难道不是么？ 为什么我 wa ？

管理员出来，我怎么一直错阿

想简单了...

好久没有更新过了

第7个点错的同志们注意了,数据中有重边的,注意判断下,否则的话割边的数量会多求.

晕了 第二问怎么做啊

NOI几时候？

竟然有新题了...

离NOI还有1天，希望再发3道押题... ^-^

终于有新题了...汗`\

---|---|---|---|---|---|

愿C语言能携手P共同发展壮大!各位学C的顶啊!!

NOIP 2007 is coming!

湖北宜昌一中110班 SixplusSeVen

QQ:383025560

blog.sina.com/NoipCenter

竟然连地板都没有了

太凶狠了……

解题报告有……呃……暂时不发

很好。使用了异或解决重边问题，修复了Gabow算法不能直接判断桥（割边）和割点的BUG。
```c++
#include<bits/stdc++.h>
#define go(i,a,b) for(register int i=a;i<=b;i++)
#define fo(i,a,x) for(register int i=a[x];i>=0;i=e[i].next)
#define In() freopen("in.in","r",stdin)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct E{int v,next;}e[50010];
stack<int>S,lowS;
int n,m,head[50010],dfn[50010],dfs_clock,k;
int num,belong[50010],BRI,out[50010],help;
void ADD(int u,int v){e[k]=(E){v,head[u]};head[u]=k++;}
void Gabow(int u,int from)
{
dfn[u]=++dfs_clock;
S.push(u);lowS.push(u);
fo(i,head,u)
{
int v=e[i].v;
if((i^1)==from)continue;
if(!dfn[v])
{
Gabow(v,i);
if(!lowS.empty()&&dfn[help]>dfn[u])
{
BRI++;
//printf("[%d]--->[%d]\n",u,v);
}
}
else if(!belong[v])
while(!lowS.empty()&&dfn[lowS.top()]>dfn[v])lowS.pop();

}
help=lowS.top();
if(!lowS.empty()&&lowS.top()==u)
{
lowS.pop();
num++;
int v;
do
{
v=S.top();S.pop();
belong[v]=num;
}while(u!=v);
}
}
int main()
{
In();
scanf("%d%d",&n,&m);mem(head,-1);
go(i,1,m)
{
int u,v;
scanf("%d%d",&u,&v);
ADD(u,v);ADD(v,u);
}
go(i,1,n)
if(!dfn[i])Gabow(i,-1);

printf("%d\n",BRI);

go(u,1,n)fo(i,head,u)
{
int v=e[i].v;
if(belong[u]!=belong[v])
out[belong[u]]++;
}

int LEAF=1;
go(i,1,num)if(out[i]==1)LEAF++;
printf("%d\n",LEAF/2);
return 0;
}

Vijos 上做过的最好的一道题。

https://blog.sengxian.com/algorithms/bcc-addedge

很久以前就研究过这个题以及它的扩展情况，没想到今天做到了这个题。这个题的精髓就是加边的数量，使用贪心来证明数量为 \(\lceil\frac{leaf + 1}{2}\rceil\)。

本题有两点要注意的：

1. 有重边。
2. 全图联通（没有孤立点）。