首页 > 其他分享 >存图方法

存图方法

时间:2023-02-28 23:11:50浏览次数:28  
标签:ch int long while 存图 include 方法 define

1.链式前向星

这个方法很有意思,充分地利用了指针的性质,实现了分散存储两个顶点的连接关系,颇有种链表的感觉。

  • 利用链式前向星存无向图
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#define ll long long
#define ull unsigned long long
//#define int long long

inline 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*10+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
const int maxm=2e5+5;
int n,head[maxm],cnt;
struct edge1{
	int to,next;
}p[maxm];

void add_edge1(int a,int b){//无向无边权 
	p[cnt].to=b;			//cnt起点,b终点 
	p[cnt].next=head[a];	//标记前面一个同起点点的位置 
	head[a]=cnt++;			//更新下标 
	return ;
}

void solve(){
	cin>>n;
	memset(head,-1,sizeof(head));//利用-1来标记是否遍历到了根节点 
	int a,b;
	cnt=0;
	for(int i=0;i<n;++i){
		cin>>a>>b;
		add_edge1(a,b);
		add_edge1(b,a);
	}
	for(int i=1;i<=n;++i){
		cout<<i<<"..."<<head[i]<<endl;
		for(int j=head[i];j>=0;j=p[j].next){//遍历的方法 
			cout<<p[j].to<<'#';
		}
		cout<<endl;
	}
	return ;
}

signed main(){
//	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int cs=1;
//	cin>>cs;
	while(cs--){
		solve();
	}
	return 0;
}

标签:ch,int,long,while,存图,include,方法,define
From: https://www.cnblogs.com/Qiansui/p/17166439.html

相关文章