Description

Blackouts and Dark Nights (also known as ACM++) is a company that provides electricity. The company owns several power plants, each of them supplying a small area that surrounds it. This organization brings a lot of problems - it often happens that there is not enough power in one area, while there is a large surplus in the rest of the country.

ACM++ has therefore decided to connect the networks of some of the plants together. At least in the first stage, there is no need to connect all plants to a single network, but on the other hand it may pay up to create redundant connections on critical places - i.e. the network may contain cycles. Various plans for the connections were proposed, and the complicated phase of evaluation of them has begun.

One of the criteria that has to be taken into account is the reliability of the created network. To evaluate it, we assume that the worst event that can happen is a malfunction in one of the joining points at the power plants, which might cause the network to split into several parts. While each of these parts could still work, each of them would have to cope with the problems, so it is essential to minimize the number of parts into which the network will split due to removal of one of the joining points.

Your task is to write a software that would help evaluating this risk. Your program is given a description of the network, and it should determine the maximum number of non-connected parts from that the network may consist after removal of one of the joining points (not counting the removed joining point itself).

Input

The input consists of several instances.

The first line of each instance contains two integers 1 <= P <= 10 000 and C >= 0 separated by a single space. P is the number of power plants. The power plants have assigned integers between 0 and P - 1. C is the number of connections. The following C lines of the instance describe the connections. Each of the lines contains two integers 0 <= p1, p2 < P separated by a single space, meaning that plants with numbers p1 and p2 are connected. Each connection is described exactly once and there is at most one connection between every two plants.

The instances follow each other immediately, without any separator. The input is terminated by a line containing two zeros.

Output

The output consists of several lines. The i-th line of the output corresponds to the i-th input instance. Each line of the output consists of a single integer C. C is the maximum number of the connected parts of the network that can be obtained by removing one of the joining points at power plants in the instance.

输入数据 1 3 3 0 1 0 2 2 1 4 2 0 1 2 3 3 1 1 0 0 0 输出数据 1 1 2 2

Source

CTU Open 2004

描述

停电与黑夜公司（也被称为 ACM++）是一家供电公司。该公司拥有若干发电厂，每个发电厂都为其周边的一小片区域供电。这种组织形式带来了很多问题 —— 经常会出现这样的情况：在一个区域电力供应不足，而在该国的其他地区却有大量的电力剩余。

因此，ACM++ 公司决定将部分发电厂的电网连接起来。至少在第一阶段，没有必要将所有发电厂都连接成一个单一的网络，但另一方面，在关键位置创建冗余连接可能是值得的 —— 也就是说，网络可能会包含回路。已经提出了各种连接方案，并且对这些方案进行评估的复杂阶段已经开始。

必须考虑的标准之一是所创建网络的可靠性。为了评估它，我们假设可能发生的最糟糕的事件是发电厂的一个连接点出现故障，这可能会导致网络分裂成几个部分。虽然这些部分中的每一个仍然可以工作，但它们中的每一个都必须应对各种问题，所以至关重要的是，要将由于移除一个连接点而导致网络分裂成的部分数量减到最少。

你的任务是编写一个软件来帮助评估这种风险。你的程序会得到网络的描述，并且它应该确定在移除一个连接点（不包括被移除的连接点本身）之后，网络可能由的不连通部分的最大数量。

输入

输入由若干个实例组成。 每个实例的第一行包含两个整数， 1≤P≤10000 和 C≥0 ，它们由一个空格分隔。 P 是发电厂的数量。发电厂被分配了 0 到 P−1 之间的整数。 C 是连接的数量。该实例接下来的 C 行描述了这些连接。每行包含两个整数 0≤p1,p2<P ，由一个空格分隔，表示编号为 p1 和 p2 的发电厂是相连的。每个连接恰好被描述一次，并且每两个发电厂之间最多只有一个连接。 这些实例紧挨着依次出现，没有任何分隔符。输入由一行包含两个 0 的行终止。

输出

输出由若干行组成。输出的第 i 行对应于输入的第 i 个实例。输出的每一行都包含一个整数 C 。 C 是通过移除该实例中发电厂的一个连接点所能得到的网络的连通部分的最大数量。

输入数据 1

3 3

0 1

0 2

2 1

4 2

0 1

2 3

3 1

1 0

0 0

输出数据 1

1

2

2

来源

2004 年 CTU 公开赛

算法标签：

图的连同量，树的结构；

题意分析:

本题的背景是一家供电公司（ACM++），它拥有多个发电厂，每个发电厂为周边小区域供电。由于不同区域可能出现电力供需不平衡的问题，公司打算连接部分发电厂的电网。在评估连接方案时，需要考虑网络的可靠性。 评估可靠性的一个重要标准是：假设最糟糕的情况是某个发电厂的连接点出现故障，这可能导致网络分裂成多个部分。要求编写程序，对于给定的网络连接描述，计算移除任意一个连接点（不包含被移除的连接点本身）后，网络所能形成的不连通部分的最大数量。 输入数据包含多个实例，每个实例的第一行给出两个整数 P 和 C ，其中 P 表示发电厂的数量（编号从 0 到 P−1 ）， C 表示连接的数量。接下来的 C 行，每行包含两个整数 p1 和 p2 ，表示编号为 p1 和 p2 的发电厂相连。输入以一行两个 0 结束。 输出要求针对每个输入实例，输出移除一个连接点后网络所能形成的不连通部分的最大数量。

解题思路:

求原来图的连通分支数+割点数，在模板上修改一点就好了，转一个挺不错的解释： 在dfs的时候，我们用cut[i]==X表示在dfs树中当i节点被删除时，i节点的X个儿子被切割开来(可以认为cut[i]是i节点与它的儿子连接的桥边的数目)。注意：如果i是根且其儿子只有1个,虽然i不是割点,cut[i]依然=1。如果i节点非割点,那么cut[i]=0。如果i是割点，那么cut[i]就是i被删除后将割出来的儿子数目。 然后我们求出了每个点的cut[i]值，即i点被删除，会有cut[i]个儿子树被割出来。如果i是dfs树的非根节点，那么cut[i] 切除i之后增加的连通分量数目。如果i是dfs树的根节点，那么cut[i]-1才是切除i之后增加的连通分量数目(想想是不是)。 如果原始cut[i]=0,表示i是孤立的一点,此时cut[i]-1=-1. 如果原始cut[i]=1,表示i为根且有一个儿子,此时cut[i]-1=0. 如果原始cut[i]>=2,表示i为根且分割了>=2个儿子,此时cut[i]-1>=1. 我个人理解为cnt[i]为切掉该点新生成的子树个数，为什么要减一呢，因为切掉之后是原本就有原图的那一个连通块包含在里面了，所以减一。

标程

//题意：给你一个无向图不保证是连通的，去掉某一个顶点之后，询问最多可以形成的分支数目。
//思路：
//1.处理孤立点的情况
//2.利用tarjan求解去掉的顶点，然后满足条件(最多).
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 10001
typedef vector<int>::iterator it;
vector<int> g[maxn];
int dfn[maxn],low[maxn];
bool vit[maxn];
int n,idx,sons;
int ans;
void dfs(int u,bool root)
{
    vit[u]=1;
    dfn[u]=low[u]=++idx;
    int child=0;
    for(it i=g[u].begin(); i!=g[u].end(); ++i)
    {
        int v=*i;
        if(!dfn[v])
        {
            dfs(v,false);
            low[u]=min(low[u],low[v]);
            if(root)
                sons++;
            else if(low[v]>=dfn[u])
                child++;
        }
        else low[u]=min(low[u],dfn[v]);
    }
    ans=max(ans,child+1);//low[v]>=dfn[u]得到的是child+1个支点
}
int tarjan(int root)
{
    if(g[root].size()==0)
        return 0;
    memset(dfn,0,sizeof(dfn));
    ans=idx=sons=0;
    dfs(root,true);
    if(sons>1)
        ans=max(ans,sons);
    return ans;
}
int main()
{
    int m,u,v;
    while(scanf("%d%d",&n,&m)!=EOF && n)
    {
        for(int i=0; i<n; i++)
            g[i].clear();
        while(m-->0)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        memset(vit,0,sizeof(vit));
        int ma=0,total=0;
        for(int i=0; i<n; i++)
            if(!vit[i])
                total++,ma=max(ma,tarjan(i));//求解分支的个数和判断删除一个点之后，所分割的最大值ma.
        printf("%d\n",total+ma-1);
    }
    return 0;
}