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