首页 > 其他分享 >【笔记】判环

【笔记】判环

时间:2023-11-15 19:38:30浏览次数:39  
标签:判环 dfs int cin 笔记 ++ low huan

【笔记】判环

整理一下主流且比较好写的两种方法:

一、Tarjan(有无向图都推荐这种写法)

有向图就用强连通分量,无向图的话同样魔改一下:每一条边不能反着再走一遍。

有向图:

#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=1e4+5,M=1e5+5;
struct node{ int v,ne; }e[M<<1];
int first[N],idx=0,dfn[N],low[N],n,m,scc[N],sum=0,num=0,cnt=0;
bool instk[N];
stack<int> stk;
inline void add(int x,int y){ e[++idx]=(node){y,first[x]}; first[x]=idx; }
inline void dfs(int u,int f){
	dfn[u]=low[u]=++cnt; instk[u]=1; stk.push(u);
	for(int i=first[u];i;i=e[i].ne){
		int v=e[i].v;
		if(!dfn[v]) dfs(v,u),low[u]=min(low[u],low[v]);
		else if(instk[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		int x; ++num;
		do{
			x=stk.top();
			scc[x]=num;
			instk[x]=0;
			stk.pop();
		}while(x!=u); 
		++sum;
	}
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m; int u,v; 
	F(i,1,m) cin>>u>>v,add(u,v);
	F(i,1,n) if(!dfn[i]) dfs(i,0);
	cout<<sum<<'\n';
	F(i,1,n) cout<<scc[i]<<' ';
	return 0;
}

无向图:

#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=1e4+5,M=1e5+5;
struct node{ int v,ne; }e[M<<1];
int first[N],idx=0,dfn[N],low[N],n,m,huan[N],sum=0,num=0,cnt=0;
bool instk[N];
stack<int> stk;
inline void add(int x,int y){ e[++idx]=(node){y,first[x]}; first[x]=idx; }
inline void dfs(int u,int f){
	dfn[u]=low[u]=++cnt; instk[u]=1; stk.push(u);
	for(int i=first[u];i;i=e[i].ne){
		int v=e[i].v; if(v==f) continue;
		if(!dfn[v]) dfs(v,u),low[u]=min(low[u],low[v]);
		else if(instk[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		int x,sz=0; ++num;
		do{
			x=stk.top();
			huan[x]=num;
			instk[x]=0;
			++sz;
			stk.pop();
		}while(x!=u); 
		if(sz>1) ++sum;
	}
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m; int u,v; 
	F(i,1,m) cin>>u>>v,add(u,v),add(v,u);
	F(i,1,n) if(!dfn[i]) dfs(i,0);
	cout<<sum<<'\n';
	F(i,1,n) cout<<huan[i]<<' ';
	return 0;
}

二、Topsort

注意topsort一遍之后的图上得每一个点不一定都在环上。

简单来说,topsort 只能去掉进环的所有点和边,而不能去掉出环的点和边。

怎么解决能,此时就可以类似染色的标记每一个点,如果当前点或它的儿子继续往下走能遇到一个已经染过色的点的话,那它就真的在环上。否则不在。

有向图就是先 topsort ,再依次访问每个块,并标记真正在环上的点。

无向图的话魔改一下 topsort:改为“每次将入度为1的点加入队列中”。并且 dfs 时不允许 v 沿着来时的反边走回 u.

有向图:

#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=1e4+5,M=2e5+5;
struct node{ int v,ne;}e[M<<1];
int first[N],huan[N],in[N],idx=0,n,m,num=0;
bool vis[N];
inline void add(int x,int y){ e[++idx]=(node){y,first[x]}; first[x]=idx; }
inline void topsort(){
	queue<int>q;
	F(i,1,n) if(!in[i]) q.push(i);
	while(q.size()){
		int u=q.front(); q.pop(); vis[u]=1;
		for(int i=first[u];i;i=e[i].ne){
			int v=e[i].v;
			if(!(--in[v])) q.push(v);
		}
	}
}
inline void dfs(int u){
	vis[u]=1; int rp=0; 
	for(int i=first[u];i;i=e[i].ne) {
		int v=e[i].v;
		if(!vis[v]) {
			dfs(v);
			if(!huan[u] && huan[v]) huan[u]=huan[v];
			//注意不能直接huan[u]=huan[v] 
			//只要任意一个u的儿子在当前环上,那么u就在环上 
		}
		else huan[u]=num;
	}
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int u,v;
	cin>>n>>m; F(i,1,m) cin>>u>>v,add(u,v),++in[v];
	topsort();
	F(i,1,n) if(!vis[i]) ++num,dfs(i);
	F(i,1,n) if(!huan[i]) huan[i]=++num;
	F(i,1,n) cout<<huan[i]<<' ';
	return 0;
}

无向图:

#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=1e4+5,M=2e5+5;
struct node{ int v,ne;}e[M<<1];
int first[N],huan[N],in[N],idx=0,n,m,num=0;
bool vis[N];
inline void add(int x,int y){ e[++idx]=(node){y,first[x]}; first[x]=idx; }
inline void topsort(){
	queue<int>q;
	F(i,1,n) if(in[i]==1) q.push(i);
	while(q.size()){
		int u=q.front(); q.pop(); vis[u]=1;
		for(int i=first[u];i;i=e[i].ne){
			int v=e[i].v;
			if(--in[v]==1) q.push(v);//区别1
		}
	}
}
inline void dfs(int u,int f){
	vis[u]=1; int rp=0; 
	for(int i=first[u];i;i=e[i].ne) {
		int v=e[i].v; if(v==f) continue;//区别2
		if(!vis[v]) {
			dfs(v,u);
			if(!huan[u] && huan[v]) huan[u]=huan[v];
			//注意不能直接huan[u]=huan[v] 
			//只要任意一个u的儿子在当前环上,那么u就在环上 
		}
		else huan[u]=num;
	}
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int u,v;
	cin>>n>>m; F(i,1,m) cin>>u>>v,add(u,v),add(v,u),++in[v],++in[u];
	topsort();
	F(i,1,n) if(!vis[i]) ++num,dfs(i,0);
	F(i,1,n) if(!huan[i]) huan[i]=++num;
	F(i,1,n) cout<<huan[i]<<' ';
	return 0;
}

标签:判环,dfs,int,cin,笔记,++,low,huan
From: https://www.cnblogs.com/superl61/p/17834576.html

相关文章

  • 11.15每日总结(阅读笔记5)
    《人月神话》是一部我近期阅读的书籍,它给我留下了深刻的印象。这本书主要探讨了项目管理和人际关系之间的复杂性和挑战,让我有了许多新的思考和认识。首先,书中的每个章节都引人入胜,作者通过生动的案例和有趣的故事,让读者更好地理解了项目管理和人际关系的实质。特别是在处理项目延......
  • python初学者学习笔记-第十章-pandas
    Chapter10/pandas10.1dataframe简介dataframe是pandas中最基础的数据结构,当然它也是pandas中最常见的对象,它跟表格类似。dataframe的行和列是分别存储的数据集;这种存储方式,加快了列和行的操作效率。10.1.1创建dataframe一般情况下,可以通过列表和字典这些类型的数据源来创建......
  • openGauss学习笔记-124 openGauss 数据库管理-设置账本数据库-查看账本历史操作记录
    openGauss学习笔记-124openGauss数据库管理-设置账本数据库-查看账本历史操作记录124.1前提条件系统中需要有审计管理员或者具有审计管理员权限的角色。数据库正常运行,并且对防篡改数据库执行了一系列增、删、改等操作,保证在查询时段内有账本操作记录结果产生。124.2背景......
  • FPGA入门学习笔记001
    1、assignassign为连续赋值语句,通常用于组合逻辑电路,例如:assignled_out=(key_in==0)?a:b;2、timescale例如:`timescale1ns/1ps定义了一个仿真精度。'1ns'为仿真步进,例如设置100的延时'#100',则实际延时100*1ns。'1ps'为仿真精度,设定延时,可以精确到小数点后两位,例......
  • 【课程】算法设计与分析——第八周 题解笔记
    第八周算法题解笔记1极值点题目描述给定一个单峰函数f(x)和它的定义域,求它的极值点该单峰函数f(x)保证定义域内有且只有一个极值点,且为极大值点题解本题感觉和dp关系不大,主要思路是三分法,和二分法非常类似,但没有二分法常用,主要用途是用来求单峰函数的极值对于任意一个......
  • 【做题笔记】NOIP真题们
    [NOIP2022]种花题意不太好描述,感性理解(题意一道计数类问题。不难发现F形只需要在C形的基础上在末尾伸出一小支就好了。所以我们先考虑C形的计数方案。图形计数类一个基本的trick就是枚举拐点,因此我们考虑枚举下面这一行的拐点(也就是首个种花的位置)\((i,j)\)。令上面......
  • Python3 协程 await async 相关的用法和笔记
    想要提供可以进行协程切换的awaitable,可以使用下面的方法:1任务taskasyncdeffunc():print("yesWait")task=asyncio.create_task(func())awaittask2协程对象,可以使asyncdef定义的协程函数(是否能触发切换不一定,要看函数内容)函数内可以利用asyncio.sl......
  • 图论——最小生成树 学习笔记
    图论——最小生成树学习笔记本文仅对于无向连通图。生成树,SpanningTree(ST),在一个\(n\)个点的图中选取\(n-1\)条边,构成一棵树。最小生成树,MinimumSpanningTree(MST),通常是边权和最小的生成树。算法分类:算法PrimPrim堆优化Kruskal思想加点加点加边时间......
  • 第十二章学习笔记、知识完整性总结
    摘要:本章讨论了块设备I/O和缓冲区管理;解释了块设备I/O的原理和I/O缓冲的优点;论述了Unix的缓冲区管理算法,并指出了其不足之处;还利用信号量设计了新的缓冲区管理算法,以提高I/O缓冲区的缓存效率和性能;表明了简单的PV算法易于实现,缓存效果好,不存在死锁和饥饿问题;还提出了一个......
  • 学习笔记419—如何快速从Github下载文件
    如何快速从Github下载文件从国内下载Github文件的速度往往会很慢,因此有一些开发者提供了代理下载功能,这些服务都是免费的,你甚至可以通过开源代码自建Github下载官网:https://d.serctl.com这是一个简单干脆的Github文件代下网站,提供八个下载节点,你可以从中选择最快的节点下载 使用方......