#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=
10000+
100;
int n,m;
int cnt;
vector<
int>
g[maxn];
struct note
{
int v;
int num;
bool operator <(
const note &p)
const
{
return num>p.num||num==p.num&&v<
p.v;
}
}aa[maxn];
int cut[maxn];
int nn;
int low[maxn],pre[maxn];
int dfs(
int u,
int fa)
{
int lowu=pre[u]=++
nn;
int child=
0;
for(
int i=
0;i<g[u].size();i++
)
{
int v=
g[u][i];
if(!
pre[v])
{
child++
;
int lowv=
dfs(v,u);
lowu=
min(lowu,lowv);
if(lowv>=pre[u])
//大于等于u的节点分支数量就是去掉u后分为联通块的个数-1
cut[u]++
;
}
else if(pre[v]<pre[u]&&v!=
fa)
{
lowu=
min(lowu,pre[v]);
}
}
if(fa==-
1&&child==
1) cut[u]=
0;
low[u]=
lowu;
cnt++
;
aa[cnt].v=
u;
aa[cnt].num=
cut[u];
return lowu;
}
void init()
{
cnt=nn=
0;
memset(pre,0,
sizeof(pre));
memset(low,0,
sizeof(low));
for(
int i=
0;i<=n;i++
)
{
g[i].clear();
pre[i]=low[i]=cut[i]=
0;
}
}
int main()
{
while(~scanf(
"%d%d",&n,&m)&&(m+
n))
{
init();
int u,v;
while(~scanf(
"%d%d",&u,&v)&&u!=-
1)
{
g[u].push_back(v);
g[v].push_back(u);
}
for(u=
0;u<n;u++
)
if(!
pre[u])
{
dfs(u,-
1);
}
sort(aa+
1,aa+n+
1);
for(
int i=
1;i<=m;i++
)
{
printf("%d %d\n",aa[i].v,aa[i].num+
1);
}
printf("\n");
}
return 0;
}
转载于:https://www.cnblogs.com/Wangwanxiang/p/9255500.html
