58      阿里云  技术社区[云栖]

zoj 2588 Burning Bridges 边联通性

  最基本的找桥，要注意0的情况，不用输出空行，zoj现在真慢

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define Maxm 200005
#define Maxn 10005
int first[Maxm];
int U[Maxm];
int num[Maxm];
int next[Maxm];
int vis[Maxn],low[Maxn],dph[Maxn];
vector<int> ans;
int cnt;
void add(int v,int u)
{
    cnt++;
    for(int i=first[v];~i;i=next[i])
        if(U[i]==u)//重边处理
        {
            num[i]++;
            return;
        }
    next[cnt]=first[v];
    first[v]=cnt;
    U[cnt]=u;
    num[cnt]=1;

}
int dfs(int v,int f,int d)
{
    vis[v]=1;
    low[v]=dph[v]=d;
    for(int i=first[v];~i;i=next[i])
    {
        int &u=U[i];
        if(vis[u])
        {
            if(u!=f)low[v]=min(low[v],dph[u]);
        }
        else
        {
            dfs(u,v,d+1);
            if(low[u]>dph[v]&&num[i]==1)//num[i]>1为有重边
                ans.push_back(i|1);
            low[v]=min(low[u],low[v]);
        }
    }
}
int main()
{
    int T;
    int n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        int i;
        int a,b;
        memset(vis,0,sizeof(vis));
        memset(first,-1,sizeof(first));
        cnt=-1;
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            add(a,b);add(b,a);
        }
        ans.clear();
        dfs(1,-1,0);
        sort(ans.begin(),ans.end());
        printf("%d\n",ans.size());
        if(ans.size())printf("%d",(ans[0]+1)/2);
        for(i=1;i<ans.size();i++)
            printf(" %d",(ans[i]+1)/2);
        if(ans.size())puts("");
        if(T)puts("");
    }
}

最后更新：2017-04-03 16:49:02

  上一篇： 好电影推荐

  下一篇： 知识共享图文直播---（一）将数据库中的数据加载到MSFlexGrid控件中再导入Excel