程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ3177 Redundant Paths (雙聯通縮點)

POJ3177 Redundant Paths (雙聯通縮點)

編輯：C++入門知識

POJ3177 Redundant Paths (雙聯通縮點)

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

一個有橋的連通圖要變成邊雙連通圖的話，把雙連通子圖收縮為一個點，形成一顆樹。需要加的邊為(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