简单图可平面图判定

题目描述

给出一个 \(n\) 个点，\(m\) 条边的简单图，判断该图是否为可平面图。

输入格式

第一行输入两个正整数 \(n\),\(m\)。
下面 \(m\) 行每行输入两个正整数 \(u\),\(v\) 表示 \(u\) 到 \(v\) 有一条边。

输出格式

第一行输出是否为可平面图。是的话输出1，不是的话输出0。

备注

点的编号均大于0小于等于 \(n\)。

思路

首先调用Tarjan算法计算出图中所有的块。对于每一个块，要么为只含一条边的子图，要么为一个2连通图。只含一条边的图必然可平面，我们只需将其余所有的块分别用DMP算法判定是否可平面，如果全部块都可平面，则整个图可平面，否则不可平面。

参考代码

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<list>
#include<utility>
#include<algorithm>
#include<stack>
using namespace std;

int ti = 0;
int n, m, m1;
bool f = true;

struct Node
{
	int d;
	int low;
	bool vis = false;
	int pa = -1;
	int children = 0;
};

vector<vector<int>>g_all;
vector<Node>node;
stack<pair<int, int>>st;
vector<vector<int>>g;

void dfs_circle(int start, int cur, int pa, vector<bool>& vis, vector<int>& t, set<pair<int, int>>& E, unordered_set<int>& V)
{
	if (E.size() > 0)
		return;
	t.push_back(cur);
	if (cur == start && vis[cur])
	{
		for (int i = 0; i < t.size() - 1; i++)
		{
			E.insert({ min(t[i],t[i + 1]),max(t[i],t[i + 1]) });
			V.insert(t[i]);
		}
		return;
	}
	vis[cur] = true;
	for (int& x : g[cur])
	{
		if (!vis[x] || x == start && x != pa)
		{
			dfs_circle(start, x, cur, vis, t, E, V);
			if (E.size() > 0)
				return;
		}
	}
	t.pop_back();
}

int find(vector<int>& pa, int x)
{
	return x == pa[x] ? x : pa[x] = find(pa, pa[x]);
}

void Union(vector<int>& pa, int x, int y)
{
	int px = find(pa, x), py = find(pa, y);
	if (px != py)
		pa[px] = py;
}

void find_H(vector<vector<pair<int, int>>>& B, set<pair<int, int>>& E, unordered_set<int>& V)
{
	vector<pair<int, int>>all_b; //剩余所有边
	for (int i = 1; i <= n; i++)
		for (int& x : g[i])
			if (i < x && !E.count({ i,x }))
				all_b.push_back({ i,x });

	int num = all_b.size();
	vector<int>pa(num);
	for (int i = 0; i < num; i++)
		pa[i] = i;
	for (int i = 0; i < num - 1; i++)
		if (!V.count(all_b[i].first) || !V.count(all_b[i].second))
			for (int j = i + 1; j < num; j++)
				if (!V.count(all_b[j].first) || !V.count(all_b[j].second))
				{
					if (all_b[i].first == all_b[j].first && !V.count(all_b[i].first)
						|| all_b[i].first == all_b[j].second && !V.count(all_b[i].first)
						|| all_b[i].second == all_b[j].first && !V.count(all_b[i].second)
						|| all_b[i].second == all_b[j].second && !V.count(all_b[i].second)
						)
						Union(pa, i, j);
				}

	unordered_set<int>ss;
	for (int i = 0; i < num; i++)
		ss.insert(find(pa, i));
	B.resize(ss.size());
	unordered_map<int, int>mp;
	int idx = 0;
	for (auto& c : ss)
		mp[c] = idx++;

	for (int i = 0; i < num; i++)
		B[mp[find(pa, i)]].push_back(all_b[i]);
}


void dfs_road(int start, int cur, vector<int>& road, unordered_map<int, vector<int>>& bg,
	unordered_set<int>& vis, unordered_set<int>& V, vector<int>& finalroad)
{
	if (finalroad.size() > 0)
		return;
	vis.insert(cur);
	road.push_back(cur);
	if (V.count(cur) && cur != start)
	{
		finalroad = road;
		return;
	}
	for (int& x : bg[cur])
		if (!vis.count(x))
		{
			dfs_road(start, x, road, bg, vis, V, finalroad);
			if (finalroad.size() > 0)
				return;
		}
	road.pop_back();
}


bool DMP()
{
	set<pair<int, int>>E; //子图的边集
	unordered_set<int>V; //子图顶点集
	vector<int>t; //开始的圈
	vector<bool>vis(n + 1);
	int s = -1;
	for (int i = 1; i <= n; i++)
		if (g[i].size() > 0)
		{
			s = i;
			break;
		}
	dfs_circle(s, s, -1, vis, t, E, V);

	vector<list<int>>f; //面
	list<int>f1(t.begin(), t.end());
	list<int>f2(f1);
	f.push_back(f1);
	f.push_back(f2);

	while (E.size() < m1)
	{
		vector<vector<pair<int, int>>>B; //H片段
		find_H(B, E, V); //找H片段

		vector<vector<int>>f_idx(B.size()); //每个H片段所在的所有面
		int index = -1;
		for (int i = 0; i < B.size(); i++)
		{
			for (int j = 0; j < f.size(); j++)
			{
				bool flag = true;
				for (auto& b : B[i])
				{
					if (V.count(b.first) && find(f[j].begin(), f[j].end(), b.first) == f[j].end())
					{
						flag = false;
						break;
					}
					if (V.count(b.second) && find(f[j].begin(), f[j].end(), b.second) == f[j].end())
					{
						flag = false;
						break;
					}
				}
				if (flag)
					f_idx[i].push_back(j);
			}
			if (f_idx[i].size() == 0)
			{
				return false;
			}
			if (f_idx[i].size() == 1)
				index = i;
		}

		if (index == -1)
			index = 0;
		int idx_f = f_idx[index][0];

		if (B[index].size() == 1)
		{
			int a = B[index][0].first, b = B[index][0].second;
			list<int>new1, new2;
			int p1 = -1, p2 = -1;
			for (int& x : f[idx_f])
			{
				if (p1 == -1)
				{
					if (x != a && x != b)
						new1.push_back(x);
					else
					{
						p1 = x;
						new1.push_back(x);
						new2.push_back(x);
					}
				}
				else if (p2 == -1)
				{
					if (x != a && x != b)
						new2.push_back(x);
					else
					{
						p2 = x;
						new1.push_back(x);
						new2.push_back(x);
					}
				}
				else
					new1.push_back(x);
			}
			new2.push_back(p1);
			f.erase(f.begin() + idx_f);
			f.push_back(new1);
			f.push_back(new2);
			E.insert({ a,b });
		}
		else //找2个固定点之间的路径
		{
			int a = -1;
			for (auto& p : B[index])
			{
				if (V.count(p.first))
				{
					a = p.first;
					break;
				}
				if (V.count(p.second))
				{
					a = p.second;
					break;
				}
			}
			unordered_map<int, vector<int>>bg;
			unordered_set<int>v;
			vector<int>road;
			vector<int>finalroad;
			for (auto& p : B[index])
			{
				bg[p.first].push_back(p.second);
				bg[p.second].push_back(p.first);
			}
			dfs_road(a, a, road, bg, v, V, finalroad);
			int b = finalroad.back();

			list<int>new1, new2;
			int p1 = -1, p2 = -1;
			for (int& x : f[idx_f])
			{
				if (p1 == -1)
				{
					if (x != a && x != b)
						new1.push_back(x);
					else
					{
						p1 = x;
						new2.push_back(x);
						if (x == a)
						{
							for (int i = 0; i < finalroad.size(); i++)
								new1.push_back(finalroad[i]);
						}
						else
						{
							for (int i = finalroad.size() - 1; i >= 0; i--)
								new1.push_back(finalroad[i]);
						}
					}
				}
				else if (p2 == -1)
				{
					if (x != a && x != b)
						new2.push_back(x);
					else
					{
						p2 = x;
						if (x == a)
						{
							for (int i = 0; i < finalroad.size(); i++)
								new2.push_back(finalroad[i]);
						}
						else
						{
							for (int i = finalroad.size() - 1; i >= 0; i--)
								new2.push_back(finalroad[i]);
						}
					}
				}
				else
					new1.push_back(x);
			}
			f.erase(f.begin() + idx_f);
			f.push_back(new1);
			f.push_back(new2);

			for (int i = 0; i < finalroad.size() - 1; i++)
			{
				V.insert(finalroad[i]);
				E.insert({ min(finalroad[i],finalroad[i + 1]),max(finalroad[i],finalroad[i + 1]) });
			}
		}
	}

	return true;
}


void dfs(int cur)
{
	node[cur].d = ++ti;
	node[cur].low = node[cur].d;
	node[cur].vis = true;
	for (int& x : g_all[cur])
	{
		int u = min(cur, x), v = max(cur, x);
		if (!node[x].vis)
		{
			st.push({ u,v });
			node[x].pa = cur;
			node[cur].children++;
			dfs(x);
			node[cur].low = min(node[cur].low, node[x].low);
			if (node[cur].pa == -1 && node[cur].children > 1 || node[cur].pa > 0 && node[x].low >= node[cur].d)
			{
				int p = -1, q = -1;
				int num = 0;
				g.clear();
				g.resize(n + 1);
				do
				{
					auto z = st.top();
					p = min(z.first, z.second), q = max(z.first, z.second);
					num++;
					g[p].push_back(q);
					g[q].push_back(p);
					st.pop();
				} while (p != u || q != v);
		
				if (num > 6)
				{
					m1 = num;
					if (!DMP())
					{
						f = false;
						return;
					}
				}
			}
		}
		else if (x != node[cur].pa)
		{
			if (node[cur].d > node[x].d)
				st.push({ u,v });
			node[cur].low = min(node[cur].low, node[x].d);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	if (n <= 4)
	{
		cout << 1;
		return 0;
	}
	if (m > 3 * n - 6)
	{
		cout << 0;
		return 0;
	}
	g_all.resize(n + 1);
	node.resize(n + 1);

	int a, b;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		g_all[a].push_back(b);
		g_all[b].push_back(a);
	}

	for (int i = 1; i <= n; i++)
	{
		if (!f)
		{
			cout << 0;
			return 0;
		}
		if (!node[i].vis)
		{
			dfs(i);
			g.clear();
			g.resize(n + 1);
			int num = st.size();
			while (!st.empty())
			{
				auto z = st.top();
				int p = z.first, q = z.second;
				g[p].push_back(q);
				g[q].push_back(p);
				st.pop();
			}
			if (num > 6)
			{
				m1 = num;
				if (!DMP())
				{
					cout << 0;
					return 0;
				}
			}
		}
	}

	cout << 1;
	return 0;
}

本栏目推荐文章
• NX2306 建模- 实体表面印字（平面，圆柱面，曲面表面的阴阳文）
• 【计算机网络】5.网络层：控制平面
• 【计算机网络】4.网络层：数据平面
• 分治-平面最近点对问题
• 平面设计 ai工具
• 华企盾DSC为平面设计公司提供数据防泄漏解决方案
• 《平面设计基础》课程考核任务书
• T403510 平面划分(Hard) 题解
• 【Lidar】基于Python的三维点云数据转二维平面+散点图绘制
• Civil 3D横断面图体积表格的奇葩问题

平面图 平面平面 平面图 平面设计 平面几何 平面vtk 平面sdn 平面图 平面 软件 平面p7883 对偶 平面图 平面 平面图 平面 性质hnoi