首页 > 其他分享 >片 - 图论 - 1

片 - 图论 - 1

时间:2024-07-27 22:09:53浏览次数:9  
标签:图论 int ll tot dfn MAXN low

欢迎来看 “片” (的简介)

由于-\(看片\)-生涯转瞬即逝,于是我选择对“\(片\)”进行一定的总结:

相信你一定看懂了

由于开始的时间有一点晚,就姑且认为我以后会慢慢补充吧......

回到总部

\(B3609\) \([图论与代数结构\) \(701]\) \(强连通分量\)

解:tarjan,强连通分量

\(\mathcal{RT}\)

点击查看代码
#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
#define endl '\n'
using namespace std;
const int MAXM=1e5+5;
const int MAXN=1e4+5;
ll n,m;
struct edge{
	ll to,nxt;
};
edge e[MAXM];
ll head[MAXN],tot=0;
void add_edge(ll u,ll v){
	++tot;
	e[tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
}
ll colsum=0,dfn[MAXN],low[MAXN],stk[MAXN],vis[MAXN],dep=0,col[MAXN];
vector <ll> ans[MAXN];
void tarjan(ll u){
	dfn[u]=++dep;
	low[u]=dep;
	stk[++stk[0]]=u;
	vis[u]=1;
	for (int i=head[u];i;i=e[i].nxt){
		ll v=e[i].to;
		if (!dfn[v]){
			tarjan(v);
			low[u]=min(low[v],low[u]);
		}
		else{
			if (vis[v]){
				low[u]=min(low[v],low[u]);
			}
		}
	}
	if (low[u]!=dfn[u]){
		return;
	}
//	cout<<u<<endl;
	++colsum;
	vis[u]=0;
	ans[colsum].push_back(u);
	while (stk[stk[0]]!=u){
		vis[stk[stk[0]]]=0;
		ans[colsum].push_back(stk[stk[0]]);
		col[stk[stk[0]]]=colsum;
		--stk[0];
	}
	--stk[0];
	col[u]=colsum;
}
bool flag[MAXN];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		ll u,v;
		cin>>u>>v;
		add_edge(u,v);
	}
	for (int i=1;i<=n;i++){
		if (!dfn[i]) tarjan(i);
	}
	for (int i=1;i<=colsum;i++){
		sort(ans[i].begin(),ans[i].end());
	}
	cout<<colsum<<endl;
	for (int i=1;i<=n;i++){
		if (!flag[col[i]]){
			for (auto a:ans[col[i]])
				cout<<a<<" ";
			flag[col[i]]=1;
			cout<<endl;
		}
		
	}
}

Tips

  1. 当发现可以建无向图的时候,不妨再想一想能否用并查集

标签:图论,int,ll,tot,dfn,MAXN,low
From: https://www.cnblogs.com/MilkingAnAloe/p/18327579

相关文章

  • 图论 最小生成树
    未完善lxy的通风报信题目链接:https://ac.nowcoder.com/acm/contest/87255/G题意:在n*m网格种需要将军队合并并且求出最少多少天可以将军队合并如果军队被挡则输出No分析:在一支军队移动时,其他军队不可移动。由于只有一个军队在某一天可以移动,所以每次合并都必须依赖......
  • 「图论」Bron-kerbosch算法
    7.21晚上加赛T2.七负我,做这题找到了性质发现需要求最大团,不会,爆搜,打假了,赛后改,对了,但时间复杂度大爆炸,看下发题解,有这么一句话:于是学习了一下。Bron-kerbosch算法-求图的最大团,极大团概念:团:每个顶点都两两相连(又叫完全子图)极大团:没有被包含在其他团中的团最大团:顶点数......
  • 图论基础与遍历算法
    图的逻辑结构及其实现图是由节点和边构成的,边分为有向边和无向边,对应有向图和无向图,逻辑结构如下:根据这个逻辑结构,我们可以实现每个节点: //节点需要存储自身的值,也需要存储与其邻接的节点 structVertex{   intval;//自身值 vector<Vertex*>neighbors;/......
  • 图论-深度优先搜索
    引入DFS全称是DepthFirstSearch,中文名是深度优先搜索,是一种用于遍历或搜索树或图的算法。所谓深度优先,就是说每次都尝试向更深的节点走。该算法讲解时常常与BFS并列,但两者除了都能遍历图的连通块以外,用途完全不同,很少有能混用两种算法的情况。DFS常常用来指代用递归函数......
  • 【图论】【模板】差分约束系统
    差分约束系统差分约束系统是将不等式组的问题转化为图论问题。前置知识判断负环例题P5960【模板】差分约束算法思路我们将\(x_u-x_v\ley_u\)换为\(x_u\lex_v+y_u\)。然后我们建立一条连接\(v,u\)(注意是\(v,u\)不是\(u,v\))权值为\(y_u\)的边。我们发......
  • 【图论】【模板】最长路、最短路
    最短路Dijkstra算法思路Dijkstra算法,采用贪心思想,在某一时刻如果\(dis\)数组中\(dis_u\)最小,那么就固定\(u\),\(dis_u\)一定是\(1\rightarrowu\)的最短路径,然后我们再通过\(u\)更新与\(u\)有边相连的\(v\),如果\(dis_v>dis_u+w\),那么\(dis_v=dis_u+w\)......
  • 【图论】【模板】判断负环
    使用SPFA算法判断负环前言判断负环是属于判定性的问题,常与二分结合起来。例题AcWing852.spfa判断负环思路可以使用SPFA进行判断。因为两点之间至多有\(n-1\)条边,所以当一个点的最短路径经过的边数大于等于\(n\)时,说明有负环。代码#include<bits/stdc++.h>......
  • 算法 图论最短路径
    零、写在前面本文讲述Dijkstra、Bellman-Ford、Floyd-Warshall算法一、分类G(graph):图V(vertex):点E(edge):边一个图可以用数学语言描述为。W(weights):权所以一个图也可以用数学语言描述为。二、作图2.1作图网站(推荐) 在线作图网站:图论作图网站GraphEditor用法:Undirected......
  • 【2024-ZR-C Day 4】图论(1)
    1.强连通分量1.1.定义在有向图中,选取一个点集\(S\),若对于\(S\)中的任意两点\(u,v\),都满足\(u\)可以到达\(v\),则称\(S\)是强连通的。强连通分量是图中一个极大的强连通的点集。性质:把一个有向图通过强连通分量缩点后,新的图是一个DAG.1.2.Kosaraju算法在无向图......
  • (nice!!!)LeetCode 3112. 访问消失节点的最少时间(图论、边的dijkstra、堆优化)
    3112.访问消失节点的最少时间思路:节点n的个数非常大,用普通的dijkstra算法对节点进行枚举是会超时的,时间复杂度为0(n^2)。这里边的数量最大为10^5,可以对边使用dijkstra算法+堆优化操作,时间复杂度为0(mlogm)。节点消失问题,只需要加一个判断条件,判断到每个节点的最小时......