专栏文章

8-7陈老师课堂总结

CCrash_Man_CHN
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miogqi07
此快照首次捕获于
2025/12/02 18:56
3 个月前
此快照最后确认于
2025/12/02 18:56
3 个月前
查看原文

关于图

1.邻接矩阵

方式：本质是用二维数组表示，点与点之间的关系
优点：查询时间很快，O(1)
缺点：空间很大，是n*n,边的数量较多的时候会导致空间过于浪费，并且在重边的时候根本存储不了，并且输出连接一个点的所有边会很慢

2.邻接表

方式：按照边存储，存入一个vector
优点：空间不会浪费，利用率高，并且可以存储重边
缺点：查询太慢

例题

U460099 结点的度

度是什么？

度就是入度+出度，入度为指向这个点的边的个数，出度为这个点出去的边的个数

题目思路

既然度都知道了度是什么，题就简单了，我们可以用两个数组统计入度和出度，最后相加即可

题目代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int in[N],out[N];
//vector<int> v[N];
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,w;
		cin>>u>>w;
		in[u]++;
		out[w]++;
	}
	for(int i=1;i<=n;i++)cout<<in[i]+out[i]<<"\n";
	return 0;
}

U460103 图的类型

看图

题目思路

了解了三种类型之后，我们把输入的点的度给统计一下，然后分类别讨论即可

题目代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,deg[N];
string solve()
{
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++)
	{
		cnt1+=(deg[i]==1);
		cnt2+=(deg[i]==2);
	}
	if(cnt2==n)return "Ring";
	else if(cnt1==2&&cnt2==n-2)return "Chain";
	else if(cnt1==n-1)return "Flower";
	return "Neither";
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		deg[u]++,deg[v]++;
	}
	cout<<solve();
	return 0;
}

B3643 图的存储

题目思路

其实就是邻接矩阵和邻接表的拼好题，只是需要将邻接表排序输出而已

题目代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;
vector<int> v[N];
int g[N][N];
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,w;
		cin>>u>>w;
		g[u][w]=1;
		g[w][u]=1;
		v[u].push_back(w);
		v[w].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<g[i][j]<<" ";
		}
		cout<<"\n";
	}
	for(int i=1;i<=n;i++)
	{
		cout<<v[i].size()<<" ";
		sort(v[i].begin(),v[i].end(),less<int>());
		for(int j=0;j<v[i].size();j++)cout<<v[i][j]<<" ";
		cout<<"\n";
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...