求大佬看看一种常数（可能）更优的存图方式

瞎想想到的一种存图方式，但是有极大可能被前人造过了，并且其常数优化很小。大佬轻喷 qwq。

我们知道 vector 存图时随机访问是很快的，但是 push_back 很慢，因为时不时要动态扩容。

这种基础写法的 P5318（有向图 DFS & BFS，

n\le10^5

，

m\le10^6

）code，五个点总用时 368 ms：

Code 1

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
int n,m,u,v,hd,tl;
vector<int> g[N];
int q[N];
bool vis[N];
void dfs(int u)
{
	cout << u << ' ';
	for (auto v : g[u])
		if (!vis[v])
		{
			vis[v] = true;
			dfs(v);
		}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1;i <= m;i++)
	{
		cin >> u >> v;
		g[u].push_back(v);
	}
	for (int i = 1;i <= n;i++)
		sort(g[i].begin(),g[i].end());
	vis[1] = true;
	dfs(1);
	cout << '\n';
	q[hd = 1] = 1;
	tl = 2;
	memset(vis,0,sizeof vis);
	vis[1] = true;
	while (hd < tl)
	{
		int u = q[hd++];
		cout << u << ' ';
		for (auto v : g[u])
			if (!vis[v])
			{
				vis[v] = true;
				q[tl++] = v;
			}
	}
}

于是有人提出把边存下来，提前处理好每个节点的度数，然后对 vector 直接 resize 即可避免动态扩容。下面是这种写法的代码，310ms。

Code 2

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
int n,m,hd,tl;
vector<int> g[N];
int cnt[N],deg[N],u[M],v[M],q[N];
bool vis[N];
void dfs(int u)
{
	cout << u << ' ';
	for (auto v : g[u])
		if (!vis[v])
		{
			vis[v] = true;
			dfs(v);
		}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1;i <= m;i++)
	{
		cin >> u[i] >> v[i];
		deg[u[i]]++;
	}
	for (int i = 1;i <= n;i++)
		g[i].resize(deg[i]);
	for (int i = 1;i <= m;i++)
		g[u[i]][cnt[u[i]]++] = v[i];
	for (int i = 1;i <= n;i++)
		sort(g[i].begin(),g[i].end());
	vis[1] = true;
	dfs(1);
	cout << '\n';
	q[hd = 1] = 1;
	tl = 2;
	memset(vis,0,sizeof vis);
	vis[1] = true;
	while (hd < tl)
	{
		int u = q[hd++];
		cout << u << ' ';
		for (auto v : g[u])
			if (!vis[v])
			{
				vis[v] = true;
				q[tl++] = v;
			}
	}
}

下面是我的思路。在上面的方法的基础上进一步优化，因为我们已经把整张图存下来了，每个节点度数都已经算好，那其实根本没必要开

n

个 vector，可以直接开一个长为

m

的内存池，记录每个

u

指向的

v

在内存池中的起始位置。相当于把元素存的更紧凑了。下面是这种方法的 298ms 的代码。

Code 3

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
int n,m,hd,tl;
int deg[N],bg[N],ed[N],g[M],tu[M],tv[M],q[N];
bool vis[N];
void dfs(int u)
{
	cout << u << ' ';
	for (int i = bg[u];i <= ed[u];i++)
	{
		int v = g[i];
		if (!vis[v])
		{
			vis[v] = true;
			dfs(v);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1;i <= m;i++)
	{
		cin >> tu[i] >> tv[i];
		deg[tu[i]]++;
	}
	bg[1] = 1;
	ed[1] = 0;
	for (int i = 2;i <= n;i++)
	{
		bg[i] = (bg[i - 1] + deg[i - 1]);
		ed[i] = bg[i] - 1;
	}
	for (int i = 1;i <= m;i++)
		g[++ed[tu[i]]] = tv[i];
	for (int i = 1;i <= n;i++)
		sort(g + bg[i],g + ed[i] + 1);
	vis[1] = true;
	dfs(1);
	cout << '\n';
	q[hd = 1] = 1;
	tl = 2;
	memset(vis,0,sizeof vis);
	vis[1] = true;
	while (hd < tl)
	{
		int u = q[hd++];
		cout << u << ' ';
		for (int i = bg[u];i <= ed[u];i++)
		{
			int v = g[i];
			if (!vis[v])
			{
				vis[v] = true;
				q[tl++] = v;
			}
		}
	}
}

求大佬看这种方法是否有一定实际用途 / 是否被前人提出过。

求大佬看看一种常数（可能）更优的存图方式

讨论操作

回复

相关推荐

求大佬看看一种常数（可能）更优的存图方式