首页 > 其他分享 >简单图可平面图判定

简单图可平面图判定

时间：2023-06-01 16:57:51浏览次数：42  
标签：node cur int 平面图 back pa 判定 图可 push

题目描述

给出一个 \(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;
}

标签：node,cur,int,平面图,back,pa,判定,图可,push
From： https://www.cnblogs.com/Mobius-strip/p/17448230.html

相关文章

  • python dig 模拟—— DGA域名判定用
     #!/usr/bin/envpythonimportdns.resolver,sysdefget_domain_ip(domain):"""GettheDNSrecord,ifany,forthegivendomain."""dns_records=list()try:#getthednsresolutionsforthisdomain......
  • python dig trace 功能实现——通过Querying name server IP来判定是否为dns tunnel
    dnstunnel确认方法，查询子域名最终的解析地址：使用方法：pythondig_trace.py "<7cf1e56b67fc90f8caaae86e0787e907>.nsconcreteblock.info"anySelectedrootnameserver: 192.203.230.10['.','info.','nsconcreteblock.info.','<......
  • DNS Tunnel判定方法
    DNSTunnel判定方法：1、查询DNS请求的域名是否存在备案； 2、查询DNS请求的域名情报信息（以及域名的alex排名）； 3、查看相同主域名下子域名编码格式及长度；（存在Base32和Base64编码且较长需要多加关注，同时xshellghostdnstunnel关注下） 4、利用浏览器做实际登陆尝试（是否正常打开......
  • 判定表
    判定表测试以判定表的形式使用测试项条件（原因）与动作（结果）之间的逻辑关系（判定规则）模型判定表通常有以下四个部分组成：1)条件桩（ConditionStub）：在左上部，列出了问题的所有条件。通常认为列出的条件的次序无关紧要。2)动作桩（ActionStub）：在左下部，列出了问题规定可能采取的操作。这些操......
  • 阅读笔记：Sybilla DLT任务重启判定系统
    论文简介Sibylla:ToRetryorNotToRetryonDeepLearningJobFailure这篇论文发表在ATC2022上，主题是提出了一个基于半监督学习的深度学习训练（DLT）作业调度的系统，该系统减少了GPU集群中不必要的作业重启操作。背景知识深度学习作业调度中的错误类型与处理机制目前的大规......
  • [SEO知识讲解] 百度判定优质内容的几个维度
    本文转载自：[SEO知识讲解]百度判定优质内容的几个维度更多内容请访问钻芒博客：https://www.zuanmang.net内容建设是seo优化人员的基础工作，如何为网站制作大量的高质量内容也是一个老生常谈的问题。实际上，在百度的眼中，网站的内容包括但不限于文字，图片，链接，多媒体信息等。在这里，重点......
  • 以点类Point及平面图形类Plane为基础设计三角形类Triangle
    以平面图形类Plane为基类公有派生三角形类Triangle，main(void)函数完成对其的测试。Point类结构说明： Point类的数据成员包括：①私有数据成员：X坐标x(double型)，Y坐标y(double型)。Point类成员函数包括：①有参构造函数Point(double,double)和拷贝构造函数Point(constPoint&)......
  • 以点类Point及平面图形类Plane为基础设计圆类Circle
    以点类Point及平面图形类Plane为基类公有派生圆类Circle，main(void)函数完成对其的测试。Point类结构说明： Point类的数据成员包括：①私有数据成员：X坐标x(double型)，Y坐标y(double型)。Point类成员函数包括：①有参构造函数Point(double,double)和拷贝构造函数Point(constPoin......
  • 基于递归最小二乘法（RLS）估算的车辆前后轮胎的侧偏刚度，如仿真结果图可知，在恒定转角，变化
    基于递归最小二乘法（RLS）估算的车辆前后轮胎的侧偏刚度，如仿真结果图可知，在恒定转角，变化车速度工况下，能够良好的估算出前后轮胎的平均刚度，该估算算法可生成代码，能够用于实车实验验证其他的算法参数需要，如横摆稳定性控制，路面附着系数估算算法等，为开发和学习节省大量时间。ID:33100694......
  • pta_【CPP0026】以点类Point及平面图形类Plane为基础设计三角形类Triangle
    #include<iostream>#include<cmath>usingnamespacestd;//点类PointclassPoint{private:doublex;doubley;public:Point(doublexv=0,doubleyv=0);/*构造函数*/Point(constPoint&p);/*拷贝构造*/~Point();/*......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99