Tyvj(无向图的桥)

摘要:
题目链接分析:无向图的桥tip这么裸的题我为什么没有一A呢因为我又把n和m搞混啦!!!

题目链接

分析:
无向图的桥

tip

这么裸的题我为什么没有一A呢
因为我又把n和m搞混啦!!!

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=210;
int n,m;
struct node{
    int x,y,nxt;
    bool p;
};
node way[1010];
int pre[N],back[N],tt=0,tot=0,st[N],an=0;
struct po{
    int x,y;
};
po ans[1010];

void add(int u,int w)
{
    tot++;
    way[tot].x=u;way[tot].y=w;way[tot].nxt=st[u];st[u]=tot;
}

int cmp(const po &a,const po &b)
{
    if (a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}

int dfs(int now,int fa)
{
    int ch=0;
    int low=pre[now]=++tt;
    for (int i=st[now];i;i=way[i].nxt)
    {
        int v=way[i].y;
        if (!pre[v])
        {
            int lowv=dfs(v,now);
            low=min(low,lowv);
            ch++;
            if (lowv>pre[now])  //存在即合理 
            {
                an++;
                ans[an].x=min(now,v);
                ans[an].y=max(now,v); 
            }  
        }
        else if (pre[v]<pre[now]&&v!=fa)
        {
            low=min(low,pre[v]);
        }
    }
    back[now]=low;
    return low;
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int u,w;
        scanf("%d%d",&u,&w);
        add(u,w);
        add(w,u);
    }
    dfs(1,-1);
    sort(ans+1,ans+1+an,cmp);
    int xx=-1;
    int yy=-1;
    for (int i=1;i<=an;i++)
        if (xx!=ans[i].x|yy!=ans[i].y)
        {
            printf("%d %d
",ans[i].x,ans[i].y);
            xx=ans[i].x;
            yy=ans[i].y;
        }
    return 0;
}

免责声明:文章转载自《Tyvj(无向图的桥)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇《JavaScript 高级程序设计》总结Tyvj-超级书架下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

IPI 通信(SMP)【转】

在MIPS架构下的IPI通信被关闭和中断后,IPIMIPS接口结构平台也将被发送_ smp_Ops{void;void;…}IPI通信是多个处理器之间的通信。send_ ipi_Single:一对一聊天send_ ipi_Mask:Mask posting,Mask表示Mask posting/*Octeon Tellanothercore of Lushi...

【转】MUD教程--巫师入门教程4

在MUD中,为了解决定时触发某种现象,一般有两种方法,一种是通过call_out()延时呼叫,另一种就是通过心跳。于是,对于要跨起离线前后的象做牢这类的事,大多都是采用condition。附:由于大多数MUD里的心跳是每两秒调一次,5+random是5至14次,因此可以看出每一个condition被调用的时间是平均19秒。然后它会按照condition的名字...

HTTP请求报文

不仅报表样式可以传递请求参数,请求url也可以以类似于键值对的方式传递数据...

Selenium操作示例——鼠标悬停显示二级菜单,再点击二级菜单或下拉列表

这两天在python中玩selenium时,我遇到了一个问题,那就是鼠标移动到页面上的一个按钮或菜单,二级菜单或下拉菜单自动弹出,然后二级菜单或者下拉列表自动点击。...

es6 proxy浅析

代理用于定义用户定义的基本操作行为,如搜索、分配、枚举、函数调用等。代理接受要代理的目标对象和一些包含元操作的对象,为要代理的对象创建“屏障”,拦截所有操作,并将其重定向到用户定义的元操作对象。然而,proxy提供了一种更好的方法来实现类似的私有属性constenablePrivate==˃newProxy(target,{has:(obj,k)=˃(!pr...

jquery跨域请求数据

Jquery跨域请求数据Jquery跨请求数据。事实上,这很容易。请遵循以下步骤:首先,编写js,通过get获取远程数据。请注意,回调参数应添加在链接之后,这意味着将回调函数地址传输到远程页面。',{params},函数cb{alert;alert;},'json');第二:编写处理程序。publicvoidProcessRequest{context.Re...