首页 > 代码库 > ZOJ 2588 Burning Bridges（判断割边）

ZOJ 2588 Burning Bridges（判断割边）

2024-07-19 16:47:38   217人阅读

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2588

题意：

Ferry王国是一个漂亮的岛国，一共有N个岛国、M座桥，通过这些桥可以从每个小岛都能
到达任何一个小岛。很不幸的是，最近Ferry王国被Jordan征服了。Jordan决定烧毁所有的桥。
这是个残酷的决定，但是Jordan的谋士建议他不要这样做，因为如果烧毁所有的桥梁，他自己的
军队也不能从一个岛到达另一个岛。因此Jordan决定烧尽可能多的桥，只要能保证他的军队能从
任何一个小岛都能到达每个小岛就可以了。
现在Ferry王国的人民很想知道哪些桥梁将被烧毁。当然，他们无法得知这些信息，因为哪
些桥将被烧毁是Jordan的军事机密。然而，你可以告知Ferry王国的人民哪些桥肯定不会被烧毁。
输入描述：
输入文件中包含多个测试数据。输入文件中第1行为一个整数T，1≤T≤20，表示测试数据
的数目。接下来有T个测试数据，测试数据之间用空行隔开。
每个测试数据的第1行为两个整数N和M，分别表示岛的数目和桥的数目，2≤N≤10000，
1≤M≤100000；接下来有M行，每行为两个不同的整数，为一座桥所连接的小岛的编号。注意，
两个岛之间可能有多座桥。 
图论算法理论、实现及应用
- 402 - 
输出描述：
对每个测试数据，首先在第1行输出一个整数K，表示K座桥不会被烧毁；第2行输出K个
整数，为这些桥的序号。桥的序号从1开始计起，按输入的顺序进行编号。
两个测试数据的输出之间有一个空行。

// tarjan 求割边的个数 

两个岛还可能存在多个桥的情况

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
const int N = 210;
const int maxn = 10100;
const int maxm = 221010;
const int inf = 1e8;
#define MIN INT_MIN
#define MAX 1e6
#define LL long long
#define init(a) memset(a,0,sizeof(a))
#define FOR(i,a,b) for(int i = a;i<b;i++)
#define max(a,b) (a>b)?(a):(b)
#define min(a,b) (a>b)?(b):(a)
using namespace std;
struct node
{
    int next,v,flag,id;
}edge[maxm];
int DFN[maxn],low[maxn],bnum,bianhao;
int ans[maxn],ge;
int head[maxn];
int st[maxn],en[maxn];
int cmp(const void *a,const void *b)
{
    return *(int *)a - *(int *)b;
}
void initt()
{
    memset(head,0,sizeof(head));
    bnum = 1;
    bianhao = 1;
    init(DFN);init(low);init(ans);
    ge = 0;
    init(st);init(en);
}
void add(int u,int v,int id)
{
    int i;
    for(i = head[u];i!=0;i=edge[i].next)
    {
        if(edge[i].v == v)
            break;
    }
    if(i)
    {
        edge[i].flag = 1;
        return ;
    }
    edge[bnum].v = v;

    edge[bnum].id = id;
    edge[bnum].flag = 0;
    edge[bnum].next = head[u];
    head[u] = bnum++;
}
void tarjan(int s,int father)
{
    DFN[s] = low[s] = bianhao++;
    for(int i = head[s];i!=0;i = edge[i].next)
    {
        if(DFN[edge[i].v]==0)
        {
            tarjan(edge[i].v,s);

                low[s] = min(low[s],low[edge[i].v]);
                if(DFN[s] < low[edge[i].v] && edge[i].flag==0)
                {
                    ans[ge++] = edge[i].id;
                    st[ge-1] = s;
                    en[ge-1] = edge[i].v;
                }
        }
        else if(edge[i].v != father)
        {
            low[s] = min(low[s],DFN[edge[i].v]);
        }
    }
}
int main()
{
    int t,m,n,a,b;
    scanf("%d",&t);
    while(t-- && scanf("%d%d",&n,&m))
    {
        initt();
        FOR(i,1,m+1)
        {
            scanf("%d%d",&a,&b);
            add(a,b,i);
            add(b,a,i);
        }
        tarjan(1,-1);

        printf("%d\n",ge);
        if(ge!=0)
        {
        qsort(ans,ge,sizeof(int),cmp);

        FOR(i,0,ge-1)
        {
            printf("%d ",ans[i]);
        }
            printf("%d\n",ans[ge-1]);
         /*   puts("割边是");
          FOR(i,0,ge)
           {
            printf("%d->%d\n",st[i],en[i]);
           }*/
        }
        if(t)
            cout<<endl;
    }
    return 0;
}



ZOJ 2588 Burning Bridges（判断割边）


联系
我们