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

HDU 4587 TWO NODES (雙連通割點應用)

編輯:關於C



題意:N個點(0~n-1),M條無向邊,問去掉2個點後最多的連通分塊有多少。


先去掉一個點求出各個割點,並在dfs過程中求出去掉這個割點有多少個連通分塊(將iscut[u]=true改為iscut[u]++),

這樣子第二次就可以直接找出最多的連通分塊了。


#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define M 5005
int pre[M],dfs_clock,iscut[M],low[M],bcc_cnt,bccno[M];
vectorG[M],bcc[M];
struct Edge
{
    int from,to;
}edge[M*2];
int edge_num,head[M];
void add_edge(int u,int v)
{
    edge[edge_num].from=v;
    edge[edge_num].to=head[u];
    head[u]=edge_num++;
}
int del;
int dfs(int u,int fa)
{
    int lowu=pre[u]=++dfs_clock;
    for(int i=head[u];i!=-1;i=edge[i].to)
    {
        int v=edge[i].from;
        if(v==del) continue;
        if(!pre[v])
        {
            int lowv=dfs(v,u);
            lowu=min(lowv,lowu);
            if(lowv>=pre[u])
                iscut[u]++;
        }
        else if(pre[v]

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