能给出c++代码吗
时间: 2023-10-01 11:11:27 浏览: 72
C++代码分享给大家
下面是一个使用C++实现Kuratowski定理进行判定的例子代码:
```c++
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 10010, M = 100010;
int h[N], e[M], ne[M], idx;
int q[N], d[N];
bool st[N];
int n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool check(vector<int>& state, int u, int v)
{
memset(h, -1, sizeof h);
idx = 0;
for (int i = 0; i < state.size(); i ++ )
{
int t = state[i], a = t / n, b = t % n;
if (a == u || b == u || a == v || b == v) continue;
add(a, b), add(b, a);
}
memset(d, -1, sizeof d);
int hh = 0, tt = 0;
q[0] = u, d[u] = 0, st[u] = true;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (st[j]) continue;
st[j] = true;
d[j] = d[t] + 1;
q[ ++ tt] = j;
}
}
for (int i = 0; i < state.size(); i ++ )
{
int t = state[i], a = t / n, b = t % n;
if (a == u || b == u || a == v || b == v) continue;
if (d[a] != -1 && d[b] != -1 && ((d[a] + d[b] + 1) & 1)) return false;
}
return true;
}
bool dfs(vector<int>& state)
{
int len = state.size();
if (len == 1) return true;
int t = state.back();
state.pop_back();
int u = t / n, v = t % n;
bool res = dfs(state);
if (res && check(state, u, v)) return true;
if (res && check(state, v, u)) return true;
state.push_back(t);
return false;
}
int main()
{
cin >> n >> m;
vector<int> state;
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
a --, b --;
state.push_back(a * n + b);
}
if (dfs(state)) puts("Yes");
else puts("No");
return 0;
}
```
该代码实现了一个简单的DFS算法,首先将图表示成一个状态,其中每个状态表示一条边。在判断是否为可平面图时,先尝试将每条边从图中删除,然后判断删除后的图是否为可平面图。如果是,则原图是可平面图;否则,继续考虑下一条边,直到所有的边都被考虑过。
阅读全文