P3520题解

wjyy · 2024-01-16 18:48:36 · 题解

P3520 题解

前置知识

理解为判断环，这题就是欧拉路径，使用一个 du 数组来判断是否存在欧拉图并且这题的图有可能不是连通图，需要特判一下，剩下的看代码注释吧，核心不是在于看怎么走，而是要看怎么判断起点终点。

#include <bits/stdc++.h>
#define ll long long
#define M 1100000

using namespace std;

stack<ll> s;
vector<ll> ans[M];
ll u, v, cnt, m, n, a, b, num;
ll head[M], du[M];
bool vis[M], vis2[M], viss[M];//vis[i]表示第i条边是否被删除 vis2[i]标记是否访问过i点

struct Edge
{
    ll to, Next;
} edge[M];

void add(ll u, ll v)//头插链表
{
    edge[cnt].to = v;
    edge[cnt].Next = head[u];
    head[u] = cnt++;
}
//核心dfs
void dfs(ll k)
{
    vis2[k] = true;//标记已访问过该点

    for (ll i = head[k]; i != -1; i = edge[i].Next)
    {
        if (vis[i] == false)//如果i号边还没有被删除
        {
            vis[i] = true;//删除i号边
            vis[i ^ 1] = true;//删除TA的反向边
            ll v = edge[i].to;
            dfs(v);
        }
    }

    if (viss[k] == true)//如果该点已经在栈中,说明出现环
    {
        num++;//记录环的编号
        ans[num].push_back(k);

        while (s.top() != k)//取到环起点的所有栈中点
        {
            ans[num].push_back(s.top());
            viss[s.top()] = false;//要标记的不在栈中
            s.pop();
        }

        ans[num].push_back(k);//因为是环,要加上起点
    }

    else
    {
        viss[k] = true;//如果不在栈点中,说明还没成环,加入栈
        s.push(k);
    }
}

int main()
{
    cin >> n >> m;

    memset(head, -1, sizeof(head))；//初始化

    for (ll i = 1； i <= m; i++)
    {
        cin >> u >> v >> a >> b;

        if (a != b)
        {
            add(u, v);
            add(v, u);//无向图反向存边
            du[u]++;
            du[v]++;
        }
    }

    for (ll i = 1; i <= n; i++)
    {
        if (du[i] % 2 != 0)//如果不存在欧拉回路
        {
            cout << "NIE";//再见
            return 0;
        }
    }

    for (ll j = 1; i <= n; i++)
        if (vis2[i] == false)//有可能不是连通图
            dfs(i);

    cout << num << endl;

    for (int i = 1; i <= num； i++)
    {
        cout << ans[i].size() - 1 << " ";

        for (ll j = 0; j < ans[i].size(); j++)
            cout << ans[i][j] << " ";

        cout << endl;
    }

    return 0;
}