# Railway

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2362    Accepted Submission(s): 833

Problem Description
There are some locations in a park, and some of them are connected by roads. The park manger needs to build some railways along the roads, and he would like to arrange tourist routes to each circuit. If a railway belongs to more than one tourist routes, there might be clash on it, and if a railway belongs to none tourist route, it doesn’t need to build.
Now we know the plan, and can you tell us how many railways are no need to build and how many railways where clash might happen.

Input
The Input consists of multiple test cases. The first line of each test case contains two integers, n (0 < n <= 10000), m (0 <= m <= 100000), which are the number of locations and the number of the railways. The next m lines, each line contains two integers, u, v (0 <= u, v < n), which means the manger plans to build a railway on the road between u and v.
You can assume that there is no loop and no multiple edges.
The last test case is followed by two zeros on a single line, which means the end of the input.

Output
Output the number of railways that are no need to build, and the number of railways where clash might happen. Please follow the format as the sample.

Sample Input
8 10
0 1
1 2
2 3
3 0
3 4
4 5
5 6
6 7
7 4
5 7
0 0

Sample Output
1 5

### AC代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#define max 10010
using namespace std;

vector <int> edge[max]; //邻接表
int stack[max],stop;    //工作栈
int block[max];         //联通分量各点标号，其中block[0]为环的点的总数
int low[max];           //记录当前搜索的强连通子图搜索树的根节点
int dfn[max];           //记录搜索到该点的时间
int ans1,ans2,n,m;
int Dindex;             //一个计数器，记录访问节点的次序
bool inbox[max];        //是否在同一个子图内

void init()
{
memset(dfn,0,sizeof(dfn));
for(int i=0; i<max; i++)
edge[i].clear();
stop=Dindex=ans1=ans2=0;
}

void deal_circle()
{
int num=0;
for(int i=1; i<=block[0]; i++)  //遍历所有点
{
for(int j=0; j<(int)edge[block[i]].size(); j++) //遍历所有点所邻接的点
{
int v=edge[block[i]][j];
if(inbox[v])
num++;    //如果v属于当前块，则将边数累加一次
}
}
num/=2; //因为每条边的顶点有两个，且都属于该块中，所以每条边被重复计算了一次
if(block[0]>num)    //如果块的边数大于点的个数，则这个块中有多个环
ans1+=num;
else if(block[0]<num)   //如果块的边数小于点个数，说明块中没有环(因为算法的关系，只会出现两个点并且无环的块，其他情况都会在之前的递归中排除)
ans2+=num;
}
void tarjan(int u)
{
dfn[u]=low[u]=++Dindex;
stack[++stop]=u;
for(int i=0; i<(int)edge[u].size(); i++)
{
int v=edge[u][i];
if(!dfn[v])    //如果邻接的该点没有被标记
{
tarjan(v);
low[u]=min(low[u], low[v]); //如果邻接点搜索结束后LOW更小，说明在v中找到一个环，然后使环中所有LOW统一
if(low[v]>=dfn[u])  //说明u的子节点没有与u的祖先相连的后向边，即u为割点
{
block[0]=0;
memset(inbox,false,sizeof(inbox));
int top;
do
{
top=stack[stop--];
block[++block[0]]=top;  //退栈出的元素在同一个块中
inbox[top]=true;
}
while(v!=top);
block[++block[0]]=u;    //在子图中加入u，整个子图构成块
inbox[u]=true;
deal_circle();
}
}
else    //找到一個环
low[u]=min(dfn[v], low[u]);
}
}

int main()
{
int a, b;
while(~scanf("%d%d",&n,&m) && (n||m) )
{
init();
for(int i=0; i<m; i++)
{
scanf("%d%d",&a,&b);
edge[a].push_back(b);   //加入一双向边
edge[b].push_back(a);
}
for(int i=0; i<n; i++)
if(!dfn[i])
tarjan(i);
printf("%d %d\n",ans1,ans2);
}
return 0;
}


### 4 只已被捕捉

• Krking Chrome | 78.0.3887.7 Windows 10/11

请问为什么在判断割点的时候没有根据”根节点有多个儿子”和”非根节点儿子的low>=本节点dfn”来区分，而只用了后者？

• 千千 Chrome | 76.0.3809.132 Windows 10/11

根节点也就是 dfs 进去的第一个节点，它的 low 与 dfn 相等且不会再被更新。

• 英语视频 Mozilla FireFox | 50.0 Windows XP

这个才是编程的经典实例

• 千千 Edge | 15.14965 Windows 10/11

昨天晚上弄懂的点双联通的Tarjan (⌒▽⌒)