M_sea

洛谷1656 炸铁路
Luogu算法先枚举断掉的边,然后判断整个图是否联通即可。至于判联通,并查集/Dijkstra/Kruskal/P...
扫描右侧二维码阅读全文
22
2017/09

洛谷1656 炸铁路

Luogu

算法

先枚举断掉的边,然后判断整个图是否联通即可。

至于判联通,并查集/Dijkstra/Kruskal/Prim……皆可

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define mp make_pair
using namespace std;
struct Edge //边
{
    int x,y;
    Edge() { this->x=this->y=0; }
}e[5010];
int root[200]; //并查集
pair<int,int> answ[5010]; //答案
int n,m;
inline int find(int k) //并查集查找根节点
{
    if (root[k]!=k) root[k]=find(root[k]);
    return root[k];
}
inline void merge(int x,int y) //合并
{
    int r1=find(x),r2=find(y);
    if (r1!=r2) root[r2]=r1;
}
inline void Init() { for (int i=1;i<=n;i++) root[i]=i; } //并查集的初始化
int main()
{
    scanf("%d%d",&n,&m);
    int u,v,num=0;
    for (int i=1;i<=m;i++)v//输入+建图
    {
        scanf("%d%d",&u,&v);
        e[i].x=u; e[i].y=v;
    }
    for (int i=1;i<=m;i++) //枚举断边
    {
        Init(); //初始化
        for (int j=1;j<=m;j++)
        {
            if (i==j) continue; //断边不连
            else merge(e[j].x,e[j].y); //合并
        }
        bool is=false;
        for (int j=2;j<=n;j++) 
            if (find(j)!=find(1))  //不在1的集合,也就是图不联通
            {
                is=true;
                break;
            }
        if (is) 
        {
            if (e[i].x<e[i].y) answ[++num]=mp(e[i].x,e[i].y); //存答案,注意u<v
            else answ[++num]=mp(e[i].y,e[i].x);
        }
    }
    sort(answ+1,answ+num+1); //排序
    for (int i=1;i<=num;i++) printf("%d %d\n",answ[i].first,answ[i].second); //输出
    return 0;
}
最后修改:2018 年 11 月 30 日 09 : 12 PM

发表评论