观察伪代码，对于每个节点总是走未走过且边权最小的边 。
首先我们要先求出求出最小生成树 \(G\)。
非最小生成树的边分为返祖边和横叉边。
接下来，分类讨论 :
设非树边的两个节点为 \(x,y\)，根据最小生成树的性质，可以得到非树边的权值 \(edge(x,y)\) 大于 \(x,y\) 在图 \(G\) 的路径上所有边的权值。
1.返祖边
以此图为例:
\(4\) 到 \(1\) 的返祖边的权值一定大于 \(edge(2,4),edge(2,1)\) 。
从 \(2\) 开始遍历，先走 \(edge(1,2)\) 这条边，遍历完子树 \(5\) 后回溯到节点 \(1\)，走 \(edge(1,4)\)，显然形成的兔变为最小生成树。
从 \(4\) 开始遍历，先走 \(edge(2,4),edge(2,1)\)，遍历完子树 \(5\) 后回溯到节点 \(1\)，不会走 \(edge(1,4)\)。
从 \(4\) 的子树的任意一个节点开始遍历， 一定先到 \(4\) 然后按上一种方式遍历，从 \(1\) 的其他子树开始遍历同理。
所以在 \(x,y\) 在图 \(G\) 的路径上的所有节点（不含 \(x,y\)）不能容纳这条返祖边 \(edge(x,y)\)。
- 横叉边
以此图为例:
证明的方法与返祖边类似，所以直接说结论： 所有非 \(x\) 或 \(y\) 子树的所有节点都不能容纳这条横叉边 \(edge(x,y)\)。
\(Code\)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,m,tot,num;
int fa[N];
int dep[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
vector < int > to[N];//树边
vector < pair < int , int > > ex;//非树边对，分为返祖边与横叉边
vector < int > exto[N];
void find_dep(int x,int fa)
{
dep[x]=dep[fa]+1;
for(int i=0; i<to[x].size(); i++)
{
static int y;
y=to[x][i];
if(y==fa)continue;
find_dep(y,x);
}
return;
}
int vis[N];
int now[N];
int could[N];
void find_exto(int x,int fa)
{
now[dep[x]]=x;
for(int i=0; i<exto[x].size(); i++)
{
static int y;
y=exto[x][i];
if(now[dep[y]]==y)
{
could[1]++;
could[now[dep[y]+1]]--;
could[x]++;
}
else
{
could[x]++;
could[y]++;
}
}
for(int i=0; i<to[x].size(); i++)
{
if(to[x][i]==fa)continue;
find_exto(to[x][i],x);
}
}
void find_add(int x,int fa)
{
could[x]+=could[fa];
for(int i=0; i<to[x].size(); i++)
{
static int y;
y=to[x][i];
if(y==fa)continue;
find_add(y,x);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)fa[i]=i;
for(int i=1; i<=m; i++)
{
static int x,y;
scanf("%d%d",&x,&y);
int fx=find(x),fy=find(y);
if(fx!=fy)
{
fa[fx]=fy;
to[x].push_back(y);
to[y].push_back(x);
}
else
{
tot++;
ex.push_back(make_pair(x,y));
}
}
find_dep(1,0);
for(int i=0; i<ex.size(); i++)
{
static int x,y;
x=ex[i].first;
y=ex[i].second;
if(dep[x]<dep[y])swap( x,y );
exto[x].push_back(y);
}
find_exto(1,0);
find_add(1,0);
for(int i=1; i<=n; i++)cout<<(could[i]==tot);
}