LOJ10100

2024-08-29 21:19:34

原题来自：CEOI 1996

一个电话线公司（简称 TLC）正在建立一个新的电话线缆网络，他们连接了若干个地点，编号分别从 1 到 N，没有两个地点有相同的号码，这些线是双向的并且能使两个地点保持通讯，每个地点的线都终结于电话交换机。每个地点都有一个电话交换机。从每个地点都能通过线缆到达其他任意的地点，然而它并不需要直接连接，它可以通过若干个交换机来到达目的地。

有时候某个地点供电出问题时，交换机就会停止工作。TLC 的工作人员意识到，除非这个地点是不可达的，否则这种情况就会发生，它还会导致一些其它的地点不能互相通讯。在这种情况下我们会称这个地点（错误发生的地方）为灾区。现在工作人员想要写一个程序统计所有灾区的数量。帮帮他们。

输入格式

输入文件包括若干组测试数据。

每一组是一个网络，每一组测试数据的第一行是地点的总数量 N。每组接下来最多有 N 行包括一个数字表示一个地点和与它相连接的地点的数字。最多 N 行可以完全描述整个网络，比如，网络中每个直接连接的两个地点被至少一行包括。一行内的所有数字都要用空格隔开。每组数据需要用单独的一个 0 结束。最后的块只有一行即 N=0。

输出格式

输出除了最后一组，其他每一组的灾区的数量，每个块用一行输出。

样例

样例输入

样例输出

1

2

数据范围与提示

N<100

___________________________________________________________

求割点的模板题目。

___________________________________________________________

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

 2 using namespace std;

 3 const int maxn=105;

 4 int n;

 5 struct edge

 6 {

 7     int u,v,nxt;

 8 }e[maxn*maxn];

 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 low[maxn],dfn[maxn],cnt,st[maxn],top,lts;

16 bool cut[maxn];

17 vector<int>lt[maxn];

18 void tarjan(int u,int rt)

19 {

20     low[u]=dfn[u]=++cnt;

21     st[++top]=u;

22     int ct=0;

23     for(int i=head[u];i;i=e[i].nxt)

24     {

25         int v=e[i].v;

26         if(!dfn[v])

27         {

28             ct++;

29             tarjan(v,rt);

30             low[u]=min(low[u],low[v]);

31             if((ct>1 && u==rt)||(u!=rt && low[v]>=dfn[u]))cut[u]=1;

32 /*

33             if(low[v]>=dfn[u])

34             {

35                 lts++;

36                 lt[lts].clear();

37                 while(st[top]!=u)lt[lts].push_back(st[top--]);

38                 lt[lts].push_back(u);

39             }

40 */

41         }

42         else low[u]=min(low[u],dfn[v]);

43     }

44 }

45 void init()

46 {

47     memset(head,0,sizeof head);

48     js=0;

49     memset(low,0,sizeof low);

50     memset(dfn,0,sizeof dfn);

51     cnt=0;

52     top=0;

53     lts=0;

54     memset(cut,0,sizeof cut);

55

56 }

57 int main()

58 {

59     while(scanf("%d",&n),n)

60     {

61         init();

62         int u,v;

63         while(scanf("%d",&u),u)

64         {

65             while(1)

66             {

67                 scanf("%d",&v);

68                 addage(u,v);addage(v,u);

69                 char c=getchar();

70                 if(c=='\n')break;

71             }

72         }

73         for(int i=1;i<=n;++i)

74             if(!dfn[i])tarjan(i,i);

75         int jss=0;

76         for(int i=1;i<=n;++i)if(cut[i])jss++;

77         printf("%d\n",jss);

78     }

79     return 0;

80 }

最新文章

热门文章