NC50404. 旅游航道
描述
输入描述
每组数据的首行有两个数m,n。星球的编号从1到m。
以下n行每行用两个整数a,b描述一条航道的信息，表示从星球a到星球b是有航道的。数据由SGOI旅游局提供，你无需担心数据有错。
输入文件以一行00为结束。
输出描述
输出文件共有C行，第i行仅有一个数，表示第i组输入数据的主要行道数目。
示例1
输入:
2 1 1 2 0 0
输出:
1
C++11(clang++ 3.9) 解法, 执行用时: 167ms, 内存消耗: 3912K, 提交时间: 2020-05-30 10:12:42
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e4+1;
int m,n;
vector<int> G[MAXN];
int dfn[MAXN];
int low[MAXN];
int clk;
int bridgeCnt;
void init()
{
for(int i=0;i<MAXN;i++)
G[i].clear();
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
clk=bridgeCnt=0;
}
void dfs(int s,int f)
{
dfn[s]=low[s]=++clk;
for(auto t:G[s])
if(t!=f)
{
if(dfn[t])
low[s]=min(low[s],dfn[t]);
else
{
dfs(t,s);
low[s]=min(low[s],low[t]);
if(low[t]==dfn[t])
bridgeCnt++;
}
}
}
int main()
{
while(cin>>m>>n&&m&&n)
{
init();
while(n--)
{
int a,b;
cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
dfs(1,-1);
cout<<bridgeCnt<<endl;
}
}