主页 / 问题 / 1202421
Accepted
Максим Фисман
Asked:2021-11-10 04:15:27 +0000 UTC2021-11-10 04:15:27 +0000 UTC

如何检查一个图是否是欧拉图，顶点之间的边是已知的

  • 772

这个问题具有教育意义，但包含我的想法和我自己的半工作解决方案

锻炼：

给定一个由编号点和它们之间的线组成的模式。编写一个程序，它会告诉您是否可以在不举手且不画线两次的情况下绘制此图（在所有点和线上画一支笔）？

输入： 第一行包含数字 NNN - 点数（从 0 到 1000 的数字）。
第二行包含数字 MMM - 行数（从 0 到 1000 的数字）。
接下来是 MMM 线，每条线都包含由线连接的点数对（点从 1 开始编号，一对点之间可以画几条线）

输出： Yes - 如果你能画出这样的图片，否则No

我的想法：

根据图的欧拉性质，如果满足以下条件，则图中存在欧拉路径：

  • 该图最多有 2 个奇数顶点
  • 除了可能的一个之外，所有连接的组件都不包含边。

因此，需要做的就是在数组中写入每个顶点有多少条边，计算奇数顶点的数量，如果超过 2 个，则返回 No，否则返回 Yes。这是第一个条件。现在我有这样的代码通过 9/10 测试（除了 4）。

我的代码：

int main () {
    int n, m;
    cin >> n >> m;
    int num[n+1];
    
    for (int i = 1; i <= n; i++) num[i] = 0;
    
    int a;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < 2; j++) {
            cin >> a;
            num[a]++;
        }
    }
    
    int oddNum = 0;
    bool answer = true;
    for (int i = 0; i < n; i++) {
        if (num[i] == 0) { answer = false; break; }
        else if (num[i] % 2 != 0) oddNum++;
        
    }
    if (answer) {
        if (oddNum > 2) answer = false;
        else answer = true;
    }
    cout << (answer ? "Yes" : "No");
}

问题和我的想法：

我认为问题出在关于连接组件的条件的第二部分，应该不超过1，但我不知道如何检查。也许通过蛮力，试图从每个点到达所有其他点？

c++

1 个回答

  1. Best Answer

    我现在意识到在我的评论中我实际上犯了一个错误。例如，如果给定一个有 10 个顶点的图，其中 8 个通过边 1-2、2-3、...、7-8 连接成一行，其余两个顶点没有边，则该图未连接，但具有欧拉路径。

    要检查这种情况，您需要创建一个真实图形并尝试从每个顶点运行 bfs：

    int n, m;
cin >> n >> m;
vector<vector<int>> g(n); // список инцидентных ребер каждой вершины
for (int i = 0; i < m; i++)
{
    int u, v;
    cin >> u >> v;
    g[u - 1].push_back(v - 1);
    g[v - 1].push_back(u - 1);
}

// Проверка нечетности
int count_odd = 0;
for (int i = 0; i < n; i++)
    if (g[i].size() % 2 == 1)
        count_odd++;

// Подсчет количества "больших" компонент
int count_big_comp = 0;
vector<bool> use(n, false); // хранит состояния "посещенности" для всех вершин

// Перебор всех вершин для нахождения всех компонент
for (int i = 0; i < n; i++)
{
    if (use[i]) // Проверка вершины на посещенность в какой-то из прошлых компонент
        continue;
    if (g[i].size() == 0) // Проверка вершины на изолированность
        // Вообще тут по логике должна быть строка use[i] = true, но ее можно опустить
        continue;

    count_big_comp++;

    // bfs от i-той вершины
    queue<int> q;
    q.push(i);
    use[i] = true;
    
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        
        for (int to : g[v])
        {
            if (use[to])
                continue;
            q.push(to);
            use[to] = true;
        }
    }
}

if (count_odd <= 2 && count_big_comp <= 1)
    cout << "YES\n";
else
    cout << "NO\n";
    • 0

相关问题