题目描述

原题来自：CTU Open 2004

求一个图删除一个点之后，联通块最多有多少。

输入格式

多组数据。第一行两个整数　P,C  表示点数和边数。
接下来 C 行每行两个整数 ，表示 P1 与 P2 有边连接，保证无重边。读入以 0 0 结束。

输出格式

输出若干行，表示每组数据的结果。

样例

样例输入

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

样例输出

1
2
2

数据范围与提示

 P<1e4，C>=0，0<=P1，P2<P

_________________________________________

求每个点处于几个点双联通分量。

注意拆ch[ ]，存储的是当前节点删除后当前双连通分量会分成几个更小的 分量-1。

如果当前分量只有一个节点，那么对于的ch[ ]值就是-1。

所以，ans的初始值为-2。

_________________________________________

1 #include
2 using namespace std;
3 const int maxn=1e4+10;
4 const int maxm=1e6+10;
5 struct edge
6 {
7 int u,v,nxt;
8 }e[maxm];
9 int head[maxn],js;
10 void addage(int u,int v)
11 {
12 e[++js].u=u;e[js].v=v;
13 e[js].nxt=head[u];head[u]=js;
14 }
15 int n,m;
16 int low[maxn],dfn[maxn],cnt,ch[maxn];
17 void tarjan(int u,int rt)
18 {
19 low[u]=dfn[u]=++cnt;
20 int tp=0;
21 for(int i=head[u];i;i=e[i].nxt)
22 {
23 int v=e[i].v;
24 if(!dfn[v])
25 {
26 ++tp;
27 tarjan(v,rt);
28 low[u]=min(low[u],low[v]);
29 if(low[v]>=dfn[u] && u!=rt)++ch[u];
30 }
31 else low[u]=min(low[u],dfn[v]);
32 }
33 if(u==rt)ch[u]=tp-1;
34 }
35 int lts,ans;
36 void init()
37 {
38 js=0;
39 memset(e,0,sizeof e);
40 memset(low,0,sizeof low);
41 memset(head,0,sizeof head);
42 memset(dfn,0,sizeof dfn);
43 cnt=0;
44 memset(ch,0,sizeof ch);
45 lts=0;
46 ans=-2;
47 }
48 int main()
49 {
50 while(scanf("%d%d",&n,&m),n|m)
51 {
52 init();
53 for(int u,v,i=0;i<m;++i)
54 {
55 scanf("%d%d",&u,&v);
56 ++u,++v;
57 addage(u,v);
58 addage(v,u);
59 }
60 for(int i=1;i<=n;++i)
61 if(!dfn[i])tarjan(i,i),++lts;
62 for(int i=1;i<=n;++i)ans=max(ans,ch[i]);
63 printf("%d\n",lts+ans);
64 }
65 return 0;
66 }