loj10103电力

2024-09-03 10:22:22

题目描述

原题来自：CTU Open 2004

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

输入格式

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

输出格式

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

样例

样例输入

样例输出

数据范围与提示

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

_________________________________________

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

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

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

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

_________________________________________

 1 #include<bits/stdc++.h>

 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 }

最新文章

热门文章