程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ3177 Redundant Paths (雙聯通縮點)

POJ3177 Redundant Paths (雙聯通縮點)

編輯:關於C++

求對於給定一個連通圖,加多少條邊可以變成邊雙連通圖。

一個有橋的連通圖要變成邊雙連通圖的話,把雙連通子圖收縮為一個點,形成一顆樹。需要加的邊為(leaf+1)/2 (leaf為葉子結點個數)。

對於此題,有重邊但重邊不加入計算。


重邊的話,要麼在開始去掉,要麼用橋來計算入度。

因為橋不屬於任何一個邊雙連通分支,其余的邊和每個頂點都屬於且只屬於一個邊雙連通分支。對於重邊而言,只有一對邊被標記為橋,而對於所有重邊來言,belong【u】和belong【v】都是不一樣的,那麼如果用belong【u】!=belong【v】作為添加入度條件的話,毫無疑問會多加的。

這麼說的話,縮點重新建圖的話,用橋來建更好一點,這樣新圖就不會有重邊。

代碼(用橋計算):

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
#include
#include
#include
#include
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rev(i,a,b) for(int i=(a);i>=(b);i--)
#define clr(a,x) memset(a,x,sizeof a)
#define INF 0x3f3f3f3f
typedef long long LL;
using namespace std;

const int maxn=200005;
const int maxm=2000005;

struct node
{
    int u,v;
    bool operator<(const node &b)const
    {
        if(b.u!=u)return udfn[s])
            {
                bridge++;
                ecut[e]=ecut[e^1]=1;
            }
        }
        else if(ins[v[e]])low[s]=min(low[s],dfn[v[e]]);
    }
    if(low[s]==dfn[s])
    {
        int v;
        block++;
        do
        {
            v=stck[--top];
            ins[v]=false;
            belong[v]=block;
        }while(v!=s);
    }
}
void solve(int n)
{
    clr(dfn,0);
    clr(ins,0);
    indx=block=top=0;
    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(1,0);
}
void add_(int a,int b)
{
    u[ecnt]=a;
    v[ecnt]=b;
    ecut[ecnt]=0;
    nex[ecnt]=first[a];
    first[a]=ecnt++;
}
int main()
{
    int a,b;
    while(~scanf("%d%d",&n,&m))
    {
        ecnt=0;
        clr(first,-1);
        for(int i=0;i

代碼二:

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
#include
#include
#include
#include
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rev(i,a,b) for(int i=(a);i>=(b);i--)
#define clr(a,x) memset(a,x,sizeof a)
#define INF 0x3f3f3f3f
typedef long long LL;
using namespace std;

const int maxn=200005;
const int maxm=2000005;

struct node
{
    int u,v;
    bool operator<(const node &b)const
    {
        if(b.u!=u)return udfn[s])
            {
                bridge++;
                ecut[e]=ecut[e^1]=1;
            }
        }
        else if(ins[v[e]])low[s]=min(low[s],dfn[v[e]]);
    }
    if(low[s]==dfn[s])
    {
        int v;
        block++;
        do
        {
            v=stck[--top];
            ins[v]=false;
            belong[v]=block;
        }while(v!=s);
    }
}
void solve(int n)
{
    clr(dfn,0);
    clr(ins,0);
    indx=block=top=0;
    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(1,0);
}
void add_(int a,int b)
{
    u[ecnt]=a;
    v[ecnt]=b;
    ecut[ecnt]=0;
    nex[ecnt]=first[a];
    first[a]=ecnt++;
}
int main()
{
    int a,b;
    while(~scanf("%d%d",&n,&m))
    {
        ecnt=0;clr(g,false);
        clr(first,-1);
        for(int i=0;i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved