首页 > 其他分享 >图论(1)

图论(1)

时间:2024-07-02 17:54:04浏览次数:11  
标签:图论 ch vis int LL read while

图论

(一)图的存储与遍历

方法一:直接存边

方法二:邻接矩阵

用bool类型二维数组存储 \(u 是否能到 v\)

方法三:邻接表

P5318为例。

#include <bits/stdc++.h>
#define LL long long
#define ls (p<<1)
#define rs (p<<1|1)
#define INF INT_MAX
#define lowbit(x) (x&-x)
#define mod 1000000007
#define ULL unsigned long long
void write(LL x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
LL read(){
	LL x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
	return x*f;
}
using namespace std;
const int N=1e5+5;
int n,m,ans[N];
bool vis[N];
vector<int> edge[N*10];
void dfs(int x){
	vis[x]=1;
	printf("%d ",x);
	for(int y:edge[x]){
		if(vis[y]) continue;
		dfs(y);
	}
}
queue<int> q;
void bfs(int s){
	q.push(s);
	vis[s]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		printf("%d ",x);
		for(int y:edge[x]){
			if(vis[y]) continue;
			q.push(y),vis[y]=1;
		}
	}
}
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	freopen("ans.out","w",stdout);
#endif
	n=read(),m=read();
	int x,y;
	while(m--){
		x=read(),y=read();
		edge[x].push_back(y);
	}
	for(int i=1;i<=n;++i){
		sort(edge[i].begin(),edge[i].end());
	}
	dfs(1);
	puts("");
	memset(vis,0,sizeof(vis));
	bfs(1);
	return 0;
}

方法四:链式前向星

P3916为例。

#include <bits/stdc++.h>
#define LL long long
#define ls (p<<1)
#define rs (p<<1|1)
#define INF INT_MAX
#define lowbit(x) (x&-x)
#define mod 1000000007
#define ULL unsigned long long
void write(LL x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
LL read(){
	LL x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
	return x*f;
}
using namespace std;
const int N=1e5+5;
int n,m,tot,hd[N],ans[N];
struct node{
	int nxt,to;
}edge[N];
void add_edge(int u,int v){
	edge[++tot]={hd[u],v};
	hd[u]=tot;
}
void dfs(int x){
	for(int i=hd[x];i;i=edge[i].nxt){
		int y=edge[i].to;
		if(ans[y]) continue;
		ans[y]=ans[x];
		dfs(y);
	}
}
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	freopen("ans.out","w",stdout);
#endif
	n=read(),m=read();
	int x,y;
	while(m--){
		x=read(),y=read();
		add_edge(y,x);
	}
	for(int i=n;i>=1;--i){
		if(ans[i]) continue;
		ans[i]=i;
		dfs(i);
	}
	for(int i=1;i<=n;++i){
		printf("%d ",ans[i]);
	}
	return 0;
}

标签:图论,ch,vis,int,LL,read,while
From: https://www.cnblogs.com/mj666/p/18280297

相关文章

  • 图论最短路径问题与matlab实现
    上一次我们讨论了如何进行图论可视化,这一次我们通过matlab来找出图论中距离最小路径目录一、迪杰斯特拉算法(Dijkstra)二、shortestpath函数用法1.基本语法2.参数设计3.应用实例(1)输入图论信息(2)输入参数进行求解(3)最短路径可视化三、distances函数————求出任意两点的最短路径矩......
  • 图论初步与可视化
    本讲将简要介绍图论中的基本概念,并主要讲解图论中的最短路径问题。以及如何将图论可视化目录一、图论的概念二、在线作图网站1.index介绍2.NodeCount介绍3.Graphdata三、Matlab作无向图1.无权图(每条边的权重默认为1)2.利用字符串做无权图3.有权图四、Matlab作有向图一、图论的......
  • 【数据结构与算法】图论 详解
    何为完全图、稀疏图、稠密图。完全图:完全图是一种简单的无向图,其中每对不同的顶点之间都恰好有一条边。对于有n个顶点的完全图,它包含n(n-1)/2条边。在有向图中,如果任意两个顶点之间都存在方向相反的两条边,包含n(n-1)条边,则该图被称为有向完全图。稀疏图:稀疏图是边数相......
  • 【广度优先搜索 深度优先搜索 图论】854. 相似度为 K 的字符串
    本文涉及知识点广度优先搜索深度优先搜索图论图论知识汇总深度优先搜索汇总C++BFS算法LeetCode854.相似度为K的字符串对于某些非负整数k,如果交换s1中两个字母的位置恰好k次,能够使结果字符串等于s2,则认为字符串s1和s2的相似度为k。给你两个字母......
  • [学习笔记] 树链剖分 - 图论 & 数据结构
    树链剖分怎么说呢,感觉只要不是求最大最小值好像都可以用树上查分代替。例题[ZJOI2008]树的统计-单点修改树链查询树链剖分板子,不多说了,代码注意细节就行。该用dfn的地方不要把点的编号传进去。#include<bits/stdc++.h>usingnamespacestd;#definels(id<<1)#define......
  • 大厂面试高频题目——图论
    797.所有可能的路径给你一个有n个节点的有向无环图(DAG),请你找出所有从节点0到节点n-1的路径并输出(不要求按特定顺序)graph[i]是一个从节点i可以访问的所有节点的列表(即从节点i到节点graph[i][j]存在一条有向边)。思考深搜dfs模板题。classSolution:def__in......
  • 【图论】欧拉图
    欧拉回路EulerianCycle:通过图中每条边恰好一次的回路欧拉通路EulerianPath:通过图中每条边恰好一次的通路欧拉图:具有欧拉回路的图半欧拉图:具有欧拉通路但不具有欧拉回路的图欧拉图中所有顶点的度数都是偶数。若G是欧拉图,则它为若干个环的并,且每条边被包含在奇数个环内。......
  • 【数据结构】图论入门
    引入数据的逻辑结构:集合:数据元素间除“同属于一个集合”外,无其他关系线性结构:一个对多个,例如:线性表、栈、队列树形结构:一个对多个,例如:树图形结构:多个对多个,例如:图图的基本概念及术语图:G=(V,E)V:顶点(数据元素)的有穷非空集合E:边的有穷集合图的类型定义无向图:每......
  • 图论-SPFA与差分约束
    闻道有先后,术业有专攻当用来判断负环的时候,SPFA还挺好用的intpre[N];voidprint_path(ints,intt){if(s==t){cout<<s;return;}print_path(s,pre[t]);cout<<""<<t;}inthead[N],cnt;structEdge{intfrom,to,nxt,c;}e[......
  • 图论
    1图论1.1图的建立1.1.1领接表边权建图importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;publicclassMain{//定义图的邻接表表示staticList<int[]>[]g;//节点数staticintn;//保存某种状态或结果的数组......