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=

随便看看

利用adb实时查看应用日志

出现乱码解决办法:就是通过chcp命令改变代码页,UTF-8的代码页为65001,输入命令:,执行该操作后,代码页就被变成UTF-8了。...

element ui设置表格表头高度和每一行的高度

.el-table__headertr,.el-table__headerth{padding:0;height:30px;line-height:30px;}.el-table__bodytr,.el-table__bodytd{padding:0;height:30px;line-height:30px;}...

国产操作系统——银河麒麟V10 SP1使用小结

几天前,我看了国内操作系统Galaxy Kirin有了新更新的新闻,于是我开始了一个新系统=============================================个人评价:这个系统是一个国产操作系统。尽管使用了大量的Ubuntu和Windows设计,使用了Linux内核,但这是国产操作系统从无到有的开始,其意义和价值远远大于其使用价值。总之...

input框输入金额处理的解决办法

最近,已经启动的项目在删除输入输入量时突然出现问题。各种在线搜索都没有找到你想要的。今天,我将以react框架为例进行代码贡献。我会写下需求和解决方案,希望对我的朋友有用。如果有更好的方法实现它,请给我一些建议!”在“:”下;n=数学。防抱死制动系统;vars=“”;对于{s+=.replace;}S=S||“整数”;n=数学。地板对于{varp=“”;对于...

oracle的序列号(sequence)

Oracle的自动递增列应使用序列号。在初始化阶段,需要手动创建序列,然后在插入序列时手动读取分配给相关字段(如ID)的序列的nextval。这很麻烦。但是,这对于SQL Server来说不是问题,可以获得。oracle的序列号也有缓存。默认情况下,一次生成20个。如果没有用完,它们可能会丢失,这可能会导致ID不一致。此外,有时这可能会引起误解。例如,我有一...

element-ui表格el-table回显时默认全选数据

1、html代码˂el-table-columntype="selection"width="45"...