tarkjan求无向图割点模板
2024-09-29 22:37:05
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; int n,m;
const int maxn=1e5+;
const int maxm=maxn<<;
struct node
{
int to;
int nxt;
}e[maxm];
int head[maxn];
int tot;
int id;
int root;
int low[maxn];
int num[maxn];
bool vis[maxn];
int pa[maxn];
int cnt=;
int art[maxn];
void init()
{
memset(head,-,sizeof(head));
tot=;
id=;
memset(low,-,sizeof(low));
memset(num,-,sizeof(num));
memset(vis,false,sizeof(vis));
memset(pa,-,sizeof(pa));
cnt=;
memset(art,,sizeof(art));
}
void add(int u,int v)
{
e[tot].to=v;
e[tot].nxt=head[u];
head[u]=tot++;
}
void findArt(int u)
{
vis[u]=true;
low[u]=num[u]=++id;
for(int i=head[u];i!=-;i=e[i].nxt)
{
int v=e[i].to;
//树边
if(!vis[v])
{
pa[v]=u;
findArt(v);
if(low[v]>=num[u]&&u!=root)
{
art[cnt++]=u;
}
low[u]=min(low[u],low[v]);
}
else if(pa[v]!=u) //回退边
{
low[u]=min(low[u],num[v]);
}
}
} void printArt()
{
int tmp=;
for(int i=head[root];i!=-;i=e[i].nxt)
{
if(pa[e[i].to]==root) tmp++;
}
if(tmp>=) art[cnt++]=root;
for(int i=;i<cnt;i++)
{
printf("%d ",art[i]);
}
puts("");
} int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
int u,v;
for(int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
root=;
findArt(root);
printArt();
}
return ;
}
Tarkjan求无向图割点
http://www.cnblogs.com/llhthinker/p/4954082.html
最新文章
- 解析Java类和对象的初始化过程
- ios 跟踪UITextField更改的简单方法
- Android设计画面中有EditText时取消启动时自动获得焦点调用系统输入法的方法
- LCA(RMQ)
- 已有数据表的Mysql字符编码修改
- 【滚动数组】 dp poj 1036
- 基于SSE实现的极速的矩形核腐蚀和膨胀(最大值和最小值)算法。
- org.hibernate.validator.constraints.NotBlank&#39; validating type &#39;java.lang.Integer
- MySQL巧建sum索引帮我们提高至少100%的效率
- Oracle课程档案,第八天
- CNN卷积核计算
- Linux下批量修改文件名(rename)
- linux df查看硬盘使用量 du查看文件所占大小
- hdu 1.3.2 Moving Tables
- android手机如何获取手机号
- poj2506 Tiling
- Python概念-迭代器的__iter__和__next__
- RabbitMq初探——消息确认
- 技术串讲 CAS 有用
- 解决h5底部输入框在ios被软键盘顶飞 软键盘消失还下不来
热门文章
- Longest Increasing Subsequence的两种算法
- jmeter中通过beanshell访问eclipse中导出jar中的java类的方法
- vue分环境打包配置方法一
- 第1节 flume:11、flume的failover机制实现高可用
- xheditor的实例程序—类似word的编辑器
- mysql 复制中的 paxso 的两阶段和事务两阶段的区别
- javascript(函数式编程思考) --->; Map-Filter-quicksort-Collatz序列-Flodl-Flodr
- 对于WebAssembly编译出来的.wasm文件js如何调用
- 51nod——1174 区间中最大的数(ST)
- 洛谷 P1483 序列变换