tips:思想只要有任一节点的儿子可以在不同过父亲的的前提下，到达一个时间戳最小的祖先。并且满足low[g[x][i]]>=num[x]则为割点，满足low[g[x][i]]>num[x]则为割边
割点：
#include<iostream>
#include<vector>
using namespace std;
int n,m,rt;
vector<int>g[1100];
int index;//时间戳
int num[1100],low[1100];
//分别表示自身的时间戳，以及能在不经过父节点的情况下能到达的祖先中最小的时间戳
int flag[1100];
void dfs(int x,int fr)
{
int child=0;
num[x]=low[x]=++index;
for(int i=0;i<g[x].size();i++)
{
if(!num[g[x][i]])
{
child++;
dfs(g[x][i],x);
low[x]=min(low[x],low[g[x][i]]);
if(x==rt&&child==2)flag[x]=1;
if(x!=rt&&low[g[x][i]]>=num[x])flag[x]=1;//g[x][i] x
}
else if(g[x][i]!=fr)
{
low[x]=min(low[x],num[g[x][i]]);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;cin>>x>>y;
g[x].push_back(y);g[y].push_back(x);
}
dfs(1,rt=1);
for(int i=1;i<=n;i++)if(flag[i])cout<<endl<<i;
return 0;
}
测试：
6 7
1 4
1 3
4 2
3 2
2 5
2 6
5 6
结果：
2
割边：
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int num[100],low[100];
int flag[100];
int n,m,rt,index;
vector<int>g[100];
void dfs(int x,int f)
{
int child=0;
num[x]=low[x]=++index;
for(int i=0;i<g[x].size();i++)
{
if(!num[g[x][i]])
{
child++;
dfs(g[x][i],x);
low[x]=min(low[x],low[g[x][i]]);
if(low[g[x][i]]>num[x])
{
cout<<x<<"->"<<g[x][i]<<endl;
}
}
else if(g[x][i]!=f)
{
low[x]=min(num[g[x][i]],low[x]);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,z;cin>>x>>y;//>>z;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,rt=1);
for(int i=1;i<=n;i++)if(flag[i])cout<<i<<endl;
return 0;
}
/*
6 6
1 4
1 3
4 2
3 2
2 5
5 6
*/ 5->6 2->5
转载请注明原文地址: https://ju.6miu.com/read-13805.html
