旅游航道

Description
SGOI 旅游局在 SG-III星团开设了旅游业务，每天有数以万计的地球人来这里观光，包括联合国秘书长，各国总统
和 SGOI 总局局长等。旅游线路四通八达，每天都有众多的载客太空飞船在星团的星球之间来往穿梭，他们保证了
任意两个星球之间总是可以通过航道到达。但是，最近由于财政出现了困难，一些太空飞船也过于古老，又没有足
够的资金购买新产品，所有只好取消一些航道。如果某一条航道的删除使得一些星球不能到达，那么这条航道是不
能删除的，称之为「主要航道」。SGOI 旅游局局长希望知道主要航道的数目，但是航道较多，他不能手工计算，
于是，他委托你写一个程序，计算主要航道数目。
Input
输入文件包含若干组数据。
每组数据的首行有两个数m,n。星球的编号从1到m。
以下n行每行用两个整数a,b描述一条航道的信息，
表示从星球a到星球b是有航道的。
数据由 SGOI 旅游局提供，你无需担心数据有错。
输入文件以一行0为结束。
1≤n,m≤30000,1≤a,b≤m
Output
共有C行，第i行仅有一个数，表示第i组输入数据的主要行道数目。
Sample Input
2 1
1 2
0 0
Sample Output
1

sol：无向图的割边

 1 #include<bits/stdc++.h>
 2 #define N 30010
 3 using namespace std;
 4 inline int read()
 5 {
 6     int x=0,f=1;
 7     char c=getchar();
 8     while(c<'0'||c>'9')
 9     {
10         if(c=='-')
11             f=-1;
12         c=getchar();
13     }
14     while(c>='0'&&c<='9')
15     {
16         x=(x<<3)+(x<<1)+c-'0';
17         c=getchar();
18     }
19     return x*f;
20 }
21 int n,m,u,v,cnt=0,ans=0,num=0,head[N],low[N],dfn[N];
22 struct Edge
23 {
24     int to,nxt;
25 }edge[N<<1];
26 void add(int a,int b)
27 {
28     cnt++;
29     edge[cnt].to=b;
30     edge[cnt].nxt=head[a];
31     head[a]=cnt;
32 }
33 void Tarjan(int u,int fa)//u表示当前节点，fa为父亲点 
34 {
35     low[u]=dfn[u]=++num;
36     for(int i=head[u];i;i=edge[i].nxt)
37     {
38         int v=edge[i].to;
39         if(v==fa)
40             continue;
41         if(!dfn[v])//v还未被访问过 
42         {
43             Tarjan(v,u);
44             low[u]=min(low[u],low[v]);
45             if(low[v]>dfn[u])//判断割边 
46                 ans++;
47         }
48         else//v已访问过 
49             low[u]=min(low[u],dfn[v]);
50     }
51 }
52 int main()
53 {
54     while(n=read(),m=read(),n!=0&&m!=0)
55     {
56         ans=cnt=num=0;
57         memset(low,0,sizeof(low));
58         memset(dfn,0,sizeof(dfn));
59         memset(head,0,sizeof(head));
60         memset(edge,0,sizeof(edge));
61         for(int i=1;i<=m;i++)
62         {
63             u=read();
64             v=read();
65             add(u,v),add(v,u);
66         }
67         Tarjan(1,0);
68         printf("%d
", ans);
69     }
70     return 0;
71 }