首页 > 其他分享 >P8436 【模板】边双连通分量

P8436 【模板】边双连通分量

时间:2024-08-27 16:55:01浏览次数:12  
标签:连通 边双 ll dfn low P8436 500005 eg 模板

      ~~~~~      P8436 【模板】边双连通分量       ~~~~~      总题单

讲解

      ~~~~~      什么是边双连通分量?就是不包含割边的极大连通块。

      ~~~~~      怎么找边双连通分量?就是割边的时候将遍历到的点放到一个桶里,若当前边是割边,则在桶内且时间戳大于等于当前点的时间戳的点就是一个边双连通分量。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll head[4000005],egt=1;
struct Edge{ll v,nxt;}eg[4000005];
inline void adeg(ll u,ll v){
	eg[++egt]={v,head[u]};
	head[u]=egt;
}

ll n,m,tot,cnt;
ll top,stk[500005];
vector<ll>pot[500005];
vector<pair<ll,ll>>bir;
ll dfn[500005],low[500005];

void Tarjan(ll p,ll ineg){
	dfn[p]=low[p]=++tot;stk[++top]=p;
	for(ll i=head[p];i;i=eg[i].nxt){
		ll v=eg[i].v;
		if(!dfn[v]){
			Tarjan(v,i);
			low[p]=min(low[p],low[v]);
			if(low[p]>dfn[p])
				bir.push_back({p,v});
		}
		else if(i!=(ineg^1))low[p]=min(low[p],dfn[v]);
	}
	if(low[p]==dfn[p]){//重点 
		cnt++;
		while(top>=1){
			ll v=stk[top--];
			pot[cnt].push_back(v);
			if(v==p)break;
		}
	}
}

signed main(){
	ios::sync_with_stdio(false);
	
	cin>>n>>m;
	while(m--){
		ll x,y;cin>>x>>y;
		adeg(x,y);adeg(y,x);
	}
	
	for(ll i=1;i<=n;i++)
		if(!dfn[i])Tarjan(i,0);
	
	cout<<cnt<<endl;
	for(ll i=1;i<=cnt;i++){
		cout<<pot[i].size()<<" ";
		for(ll it:pot[i])
			cout<<it<<" ";
		cout<<endl;
	}
	
	return 0;
}

      ~~~~~      引用请附名 —— —— —— OMG_NOIP

标签:连通,边双,ll,dfn,low,P8436,500005,eg,模板
From: https://blog.csdn.net/MC_wansui/article/details/141606939

相关文章

  • P1656 炸铁路(割边模板)
         ~~~~~     原题链接     ~~~~~     总题......
  • 行为型设计模式-模板方法(template method)模式
    通俗示例想象一下你正在制作一杯咖啡,制作咖啡的步骤大致相同,但有些步骤可以根据个人口味进行调整,比如选择咖啡豆、添加糖和奶等。在这种情况下,可以定义一个“制作咖啡”的模板,它规定了制作咖啡的基本步骤,但将某些步骤的具体实现留给子类完成。这就是模板方法模式的一个例子......
  • P5788 【模板】单调栈
    P5788【模板】单调栈传送门题目描述给出项数为\(n\)的整数数列\(a_{1\dotsn}\)。定义函数\(f(i)\)代表数列中第\(i\)个元素之后第一个大于\(a_i\)的元素的下标,即\(f(i)=\min_{i<j\leqn,a_j>a_i}\{j\}\)。若不存在,则\(f(i)=0\)。试求出\(f(1\dotsn)\)。......
  • WPF 模板
    一、数据模板继承了ItemConrol的控件对象(如ListView、ListBox、DataGrid、TabControl等等),都可以使用数据模板DataTemplate。数据模板的作用在于决定每个Item中的数据的展示形式。普通控件通过Template属性来定义模板,而子项容器控件则通过ItemTemplate属性来定义子项模板。先创......
  • AE全套视频课程(视频+模板+练习文件)零基础必看
    视频课程超全练习文件模板完整版下载链接夸克:https://pan.quark.cn/s/54a848eb52e2如果夸克容量不足,可以参考这篇文章免费扩容 夸克网盘免费扩容......
  • 苹果cms影视海螺模板V4.0优化版整站源码
    苹果cms影视海螺模板V4.0优化版整站源码苹果CMS是一款流行的影视网站管理系统,它允许用户轻松地创建和管理自己的影视内容网站。影视海螺模板V4.0优化版是针对苹果CMS设计的一个模板,它提供了更加美观和功能丰富的界面,以及一些性能和用户体验上的优化。以下是关于苹果CMS影视海......
  • 【生日视频制作】广州塔表白字幕生日视频制作AE模板修改文字软件生成器教程特效素材【
    广州塔表白字幕生日视频制作教程AE模板改文字生成神器素材祝福怎么如何做的【生日视频制作】广州塔表白字幕生日视频制作AE模板修改文字软件生成器教程特效素材【AE模板】生日视频制作步骤:安装AE软件下载AE模板把AE模板导入AE软件修改图片或文字渲染出视频......
  • 【生日视频制作】一群美女挥手拉蓝横幅条幅AE模板修改文字软件生成器教程特效素材【AE
    一群美女挥手拉蓝条横幅生日视频制作教程AE模板修改文字生成器怎么如何做的【生日视频制作】一群美女挥手拉蓝横幅条幅AE模板修改文字软件生成器教程特效素材【AE模板】生日视频制作步骤:安装AE软件下载AE模板把AE模板导入AE软件修改图片或文字渲染出视频......
  • 海螺影视主题模板M3.1全解密版本 多功能苹果CMSv10自适应主题
    海螺影视主题模板M3.1全解密版本 多功能苹果CMSv10自适应主题海螺影视主题模板M3.1全解密版本多功能苹果CMSv10自适应主题源码介绍海螺影视主题模板M3.1是一款专为苹果CMSv10设计的自适应主题模板。该模板旨在提供一个美观、易用且功能丰富的界面,以满足影视网站的需求。模......
  • A2034热门电影视频网站模版源码 仿爱美剧网站模板源码 自适应手机端 内含 视频 资讯
    A2034热门电影视频网站模版源码 仿爱美剧网站模板源码 自适应手机端 内含 视频 资讯 留言热门电影视频网站模版源码-A2034源码介绍A2034是一款仿爱美剧网站模板的热门电影视频网站模版源码。该模版设计精美,功能齐全,支持自适应手机端浏览,为用户提供优质的视频观看体......