/ Vijos / 题库 / 桐桐的糖果计划 /

题解

40 条题解

  • 1
    @ 2016-09-04 20:50:50

    http://blog.csdn.net/cax1165/article/details/52434554
    有详解！tarjan求桥+双连通分量

    • @ 2022-05-12 21:59:01 
      #include<iostream>
#include<cstring>
using namespace std;
const int maxn=5010;
int n,m,tot,ans,sum,b[maxn],r[maxn],head[maxn];
int top,low[maxn],dfn[maxn],stack[maxn];
struct node
{
    int to;
    int next;
}e[maxn*2];
bool in[maxn];
void add_edge(int u,int v)
{
    e[tot].to=v;
    e[tot].next=head[u];
    head[u]=tot++;
}
void tarjan(int u,int fa)
{
    int v;
    dfn[u]=low[u]=++tot;
    stack[++top]=u;
    in[u]=1;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        v=e[i].to;
        if(i==(fa^1))//很重要，加括号考虑优先级
        continue;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
            ans++;
        }
        else if(in[v])
        low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        sum++;//有了上面的continue，sum就是双连通分量的个数，没有的话，sum就是强联通分量的个数。
        do
        {
            v=stack[top--];
            in[v]=0;
            b[v]=sum;
        }while(u!=v);
    }
}
int main()
{
    int x,y;
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        add_edge(x,y);//无向图建双边
        add_edge(y,x);
    }tot=0;
    tarjan(1,-1);
    cout<<ans<<endl;ans=0;
    for(int i=1;i<=n;i++)//统计出度
      for(int j=head[i];j!=-1;j=e[j].next)
      if(b[i]!=b[e[j].to])
      r[b[i]]++;
    for(int i=1;i<=sum;i++)//叶节点数为出度为1的点
    if(r[i]==1)
    ans++;
    cout<<(ans+1)/2;
    return 0;
}
  • 0
    @ 2016-07-31 16:01:00

    做这道题十分的浪费光阴。算法：tarjan, 求无向图的双连通分量。吐槽一下：
    - 第七组数据有重边。**不能把重边当作一条，因为它们可以构成一个环**。此处处理比较麻烦。
    - 根据我的提交经验来看，某些数据是有孤立点的（即图不完全联通）。但是好像本题第二问直接输出 (leafNum+1)/2 即可，不必考虑这些孤立点。我考虑之后反而错了第四组数据。

  • 0
    @ 2015-03-05 21:16:36

    题意是求割边条数,以及使得原图双连通的最少添加边数.
    题目给出的图是无向连通图.
    可以用边双Tarjan,也可以直接把边拆成点来跑割点.
    用拆边法,对于每一个代表了边的割点,它一定连接两个双连通分量,这样统计的时候就不需要建树了.

  • 0
    @ 2012-11-29 17:58:31

    按错了

    嘻嘻

    • @ 2015-06-16 15:17:26

      哈哈

  • 0
    @ 2009-09-27 20:16:54

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

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

    Accepted 有效得分：100 有效耗时：0ms

    秒杀 纪念100

  • 0
    @ 2009-09-26 09:52:01

    题目描述不清 and 有重边 and 好久才AC

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

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

    Accepted 有效得分：100 有效耗时：0ms

  • 0
    @ 2009-08-08 21:43:46

    我是题目里的桐桐 哈哈~

  • 0
    @ 2009-08-04 14:48:05

    orz fengyi

    删桥得各元素为环的一颗树，把树叶依次取首尾连接既可

    连起来既可，就是

    (叶子数+1) div 2

  • 0
    @ 2009-07-19 10:41:37

    Orz voyagec2.....

    Orz AlNo3......

  • 0
    @ 2009-06-24 08:53:15

    求完桥后想用这个方法偷懒不染色

    错了N次......

    原来有反例，大家注意下不要这样写......

    ans:=0;

    fillchar(co,sizeof(co),0);

    for i:=1 to brigetotal do

    begin

    inc(co[ ancestor[ brige[i].u ] ]);

    inc(co[ ancestor[ brige[i].v ] ]);

    end;

    for i:=1 to n do

    if co[i]=1 then inc(ans);

    writeln( (ans+1) shr 1 );

  • 0
    @ 2009-09-25 22:15:14

    蓦然回首，已经AC了！！！！！！！

  • 0
    @ 2009-05-15 22:38:47

    1.求出所有桥,并记录

    2.在原图上删去这些桥

    3.对图染色

    4.重新构图,一种颜色为一个节点,边即为桥

    桥的两端的颜色分别是A,B,AB就连条边

    5.求出所有度为1的颜色点,即最多情况下的叶子节点

    都0MS刷

  • 0
    @ 2009-03-10 02:14:30

    对于重边的判断，只需要略加修改黑书上伪代码（ifather）

    原先判断是记录父亲结点，要求被枚举的结点不可以是父亲结点

    如今记录进来时的边，要求被枚举的边不可以是进边的反向边即可

  • 0
    @ 2008-11-13 15:33:39

    第7个点为什么死活过不了。

    。。。

  • 0
    @ 2008-11-13 11:18:44

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

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

    Accepted 有效得分：100 有效耗时：0ms

    过桥+\\\\\\

  • 0
    @ 2008-11-07 22:28:52

    如果楼上的数据是正确的，第7个第1行应该是5，第2行应该是2。

    大牛们的数据是从哪弄来的？

  • 0
    @ 2008-11-05 07:17:04

    太WS了。。。。。第七个数据。。。第一行的输出应该为5.。。。而标准输出为4

    第七个数据：

    16 22

    1 3

    7 1

    5 1

    12 7

    6 3

    4 7

    8 3

    10 7

    14 6

    11 5

    9 7

    15 4

    2 6

    13 12

    8 2

    2 11

    6 1

    4 11

    1 14

    3 10

    13 16

    13 16

    画画图就知道了，我是直接求桥的，编个最裸的O（VE）的求桥的程序，第一问的答案也是5。。。。。。。。。。

    就这个地方，调了我一个下午。。。

  • 0
    @ 2008-10-28 08:21:57

    不难..看细节.居然有重边.!!

    看了题解才知道..- -调了很久..

  • 0
    @ 2008-10-22 17:41:50

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

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

    Accepted 有效得分：100 有效耗时：0ms

    用邻接表做，不用判重边

  • 0
    @ 2008-10-07 16:42:25

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

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

    Accepted 有效得分：100 有效耗时：0ms

    看的题解才过...

桐桐的糖果计划

信息

ID
1325
难度
7
分类
图结构 | 强连通分量 点击显示
标签
(无)
递交数
584
已通过
127
通过率
22%
被复制
5
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1