hdu4587 求割点变形

http://acm.hdu.edu.cn/showproblem.php?pid=4587

Problem Description

Suppose that G is an undirected graph, and the value of stab is defined as follows:

Among the expression,G-i, -j is the remainder after removing node i, node j and all edges that are directly relevant to the previous two nodes. cntCompent is the number of connected components of X independently.

Thus, given a certain undirected graph G, you are supposed to calculating the value of stab.

Input

The input will contain the description of several graphs. For each graph, the description consist of an integer N for the number of nodes, an integer M for the number of edges, and M pairs of integers for edges (3<=N,M<=5000).

Please note that the endpoints of edge is marked in the range of [0,N-1], and input cases ends with EOF.

Output

For each graph in the input, you should output the value of stab.

Sample Input

4 5
0 1
1 2
2 3
3 0
0 2

Sample Output

2
/**
hdu4587 求割点变形
题目大意:给定一个图,去掉其中哪两点后能得到最多的连通块,是多少
解题思路:枚举去掉第一个点,然后利用求割点的模板就可以求出去掉另一点后的答案,取最多即可
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=5010;

struct note
{
    int v,next;
    bool cut;
} edge[maxn*2];

int head[maxn],ip;

void init()
{
    memset(head,-1,sizeof(head));
    ip=0;
}

int low[maxn],dfn[maxn],st[maxn],dex,top;
bool inst[maxn],cut[maxn];
int add_block[maxn];
int bridge;
int n,m,now;

void addedge(int u,int v)
{
    edge[ip].v=v,edge[ip].next=head[u],head[u]=ip++;
}

void tarjan(int u,int pre)
{
    low[u]=dfn[u]=++dex;
    st[top++]=u;
    inst[u]=true;
    int son=0;
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==pre)continue;
        if(v==now)continue;
        if(!dfn[v])
        {
            son++;
            tarjan(v,u);
            if(low[u]>low[v])low[u]=low[v];
            if(low[v]>dfn[u])
            {
                bridge++;
                edge[i].cut=true;
                edge[i^1].cut=true;
            }
            if(u!=pre&&low[v]>=dfn[u])
            {
                cut[u]=true;
                add_block[u]++;
            }
        }
        else if(low[u]>dfn[v])
        {
            low[u]=dfn[v];
        }
    }
    if(u==pre&&son>1)cut[u]=true;
    if(u==pre)add_block[u]=son-1;
    inst[u]=false;
    top--;
}

int solve()
{
    memset(dfn,0,sizeof(dfn));
    memset(inst,false,sizeof(inst));
    memset(add_block,0,sizeof(add_block));
    memset(cut,false,sizeof(cut));
    dex=top=0;
    bridge=0;
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        if(i!=now&&!dfn[i])
        {
            cnt++;
            tarjan(i,i);
        }
    }
    int ans=-1;
    for(int i=0;i<n;i++)
    {
        if(i!=now)
        {
           ans=max(ans,cnt+add_block[i]);
        }
    }
    return ans;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        int ans=-1;
        for(int i=0;i<n;i++)
        {
            now=i;
            ans=max(ans,solve());
        }
        printf("%d\n",ans);
    }
    return 0;
}
时间: 02-28

hdu4587 求割点变形的相关文章

tarjan算法求割点cojs 8

tarjan求割点:cojs 8. 备用交换机 ★★   输入文件:gd.in   输出文件:gd.out   简单对比时间限制:1 s   内存限制:128 MB [问题描述] n个城市之间有通讯网络,每个城市都有通讯交换机,直接或间接与其它城市连接.因电子设备容易损坏,需给通讯点配备备用交换机.但备用交换机数量有限,不能全部配备,只能给部分重要城市配置.于是规定:如果某个城市由于交换机损坏,不仅本城市通讯中断,还造成其它城市通讯中断,则配备备用交换机.请你根据城市线路情况,计算需配备备用交换

poj1144 tarjan求割点 裸题

Network Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 11684   Accepted: 5422 Description A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N

poj1144 Network【tarjan求割点】

转载请注明出处,谢谢:http://www.cnblogs.com/KirisameMarisa/p/4319585.html   ---by 墨染之樱花 [题目链接]http://poj.org/problem?id=1144 [题目描述](半天才看明白...)给图求割点个数 [思路]直接套求割点的模板即可,就是要注意输入比较坑.代码见下,附注释 #include <iostream> #include <ios> #include <iomanip> #includ

连通分量模板:tarjan: 求割点 &amp;&amp; 桥 &amp;&amp; 缩点 &amp;&amp; 强连通分量 &amp;&amp; 双连通分量 &amp;&amp; LCA(最近公共祖先)

PS:摘自一不知名的来自大神. 1.割点:若删掉某点后,原连通图分裂为多个子图,则称该点为割点. 2.割点集合:在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合. 3.点连通度:最小割点集合中的顶点数. 4.割边(桥):删掉它之后,图必然会分裂为两个或两个以上的子图. 5.割边集合:如果有一个边集合,删除这个边集合以后,原图变成多个连通块,就称这个点集为割边集合. 6.边连通度:一个图的边连通度的定义为,最

UESTC 900 方老师炸弹 --Tarjan求割点及删点后连通分量数

Tarjan算法. 1.若u为根,且度大于1,则为割点 2.若u不为根,如果low[v]>=dfn[u],则u为割点(出现重边时可能导致等号,要判重边) 3.若low[v]>dfn[u],则边(u,v)为桥(封死在子树内),不操作. 求割点时,枚举所有与当前点u相连的点v: 1.是重边: 忽略 2.是树边: Tarjan(v),更新low[u]=min(low[u],low[v]); 子树个数cnt+1.如果low[v] >= dfn[u],说明是割点,割点数+1 3.是回边: 更新lo

uoj 67 新年的毒瘤 tarjan求割点

#67. 新年的毒瘤 Time Limit: 20 Sec  Memory Limit: 256 MB 题目连接 http://uoj.ac/problem/67 Description 辞旧迎新之际,喜羊羊正在打理羊村的绿化带,然后他发现了一棵长着毒瘤的树. 这个长着毒瘤的树可以用 n 个结点 m 条无向边的无向图表示.这个图中有一些结点被称作是毒瘤结点,即删掉这个结点和与之相邻的边之后,这个图会变为一棵树.树也即无简单环的无向连通图. 现在给你这个无向图,喜羊羊请你帮他求出所有毒瘤结点. I

UVA 315 Network(无向图求割点)

题目大意 A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N. No two places have the same number. The lines are bidirectional and always connect together two pl

(转)Tarjan应用:求割点/桥/缩点/强连通分量/双连通分量/LCA(最近公共祖先)

本文转载自:http://hi.baidu.com/lydrainbowcat/item/f8a5ac223e092b52c28d591c 作者提示:在阅读本文之前,请确保您已经理解并掌握了基本的Tarjan算法,不会的请到http://hi.baidu.com/lydrainbowcat/blog/item/42a6862489c98820c89559f3.html阅读.   基本概念:   1.割点:若删掉某点后,原连通图分裂为多个子图,则称该点为割点. 2.割点集合:在一个无向连通图中,如

poj 1144 Network 无向图求割点

Network Description A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N . No two places have the same number. The lines are bidirectional and always connect