python/TangDou/AcWing/EulerPath/P3520.md

##[$P3520$ $[POI2011]$ $SMI-Garbage$](https://www.luogu.com.cn/problem/P3520)

> [$LOJ$ $2162$ 垃圾运输 $Garbage$](https://loj.ac/s/1857935)
>**注**：$LOJ$果然是好东西，所有数据完整提供下载，真是太人性化，洛谷太垃圾了！

### 一、题目描述

有一个可以看成 **无向图** 的城市，上面有 $n$ 个点和 $m$ 条边。

每一天，有若干辆垃圾车按照 **环形** 来跑一圈。并且，**对于一辆垃圾车**， 除了起点以外不能跑两次。

一条路有 $2$ 种状态：清洁的（用 `0` 表示）或不清洁的（用 `1` 表示）。每次垃圾车经过，都会改变这条路的状态。

因为有些路上的人不交垃圾清理费，所以市长想要那些路变得不清洁；除此之外的路要清洁。那么，如何安排垃圾车，才能使得市长目的达到呢？

### 二、输入格式

输入的第一行包含两个空格分隔的正整数 $n$ 和 $m$ $（ 1 \leqslant n \leqslant 100000，1 \leqslant m \leqslant 1000000）$，表示图的点数和边数。

接下来 $m$ 行，每行包含四个空格分隔的正整数 $a,b,s,t $（ $1 \leqslant a \leqslant b \leqslant n $ , $s，t \in \lbrace0,1\rbrace$  ） ，表示一条联结结点 $a$ 与 $b$ 的边，初始颜色和目标颜色分别为 $s$ 与 $t$ 。

你可以认为若存在合法方案，则存在一个卡车经过总边数不超过 $5m$ 的方案。

对于 $60\%$ 分数的数据，有 $ m \leqslant 10000$。

### 三、输出格式

如果不存在合法方案，输出一行 `NIE`（波兰语「否」）；

否则按下列格式输出任意一种方案：

- 第一行包含一个整数 $k$，表示卡车行驶环路的总数；
- 接下来 $k$ 行，每行描述一条环路：
   - 首先是一个正整数 $k_i$ 表示环路经过的边数，后接一个空格；
  - 接下来 $ k_i + 1 $ 个空格分隔的整数，依次表示环路上结点的编号。


**样例输入**

```cpp {.line-numbers}
6 8
1 2 0 1
2 3 1 0
1 3 0 1
2 4 0 0
3 5 1 1
4 5 0 1
5 6 0 1
4 6 0 1
```

**样例输出**
```cpp {.line-numbers}
2
3 1 3 2 1
3 4 6 5 4
```
**样例图示**

![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/%7Byear%7D/%7Bmonth%7D/%7Bmd5%7D.%7BextName%7D/20230807080212.png)


### 二、题目解析

#### 知识点：欧拉回路+异或+简单环
 
结合一下样例输出，明白了：
- 因为跑一趟就会让状态变成相反的，所以，如果前后一样的，其实没必要跑，或者要跑偶数次。如果前后不一样的，就需要跑一次或者跑奇数次。
  - 如果原来是$1$，后来是$1$，或者，原来是$0$，后来是$0$，也就是红色虚线，只能走偶数数次。
  - 如果原来是$1$,后来是$0$,或者，原来是$0$,后来是$1$,也就是黑色实线，只能走奇数次。

- 题目似乎在让我们找 **简单环**，两个输出示例，一个是上面的黑色线组成的环，另一个是下面黑色线组成的环。
- 什么情况下存在合法方案，什么情况下不存在合法方案呢？
答：在以前后不一致的边抽出来建图(**黑色线**)，然后判断是不是每个点的度数都是偶数，就知道是不是每个点都在欧拉图中，如果有不存欧拉图中的，就是无法完成任务。



#### 标准正确$dfs$答案
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10, M = 2e6 + 10;

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int d[N]; // 度

vector<int> res[N]; // 每个环中有哪些节点
int rl;             // 环的数量游标

int vist[N]; // 某个点是不是访问过
int st[M];   // 边是不是访问过,用于无向图的成对变换优化

vector<int> stk; // 找不用的栈
int instk[N];    // 节点i是不是在栈内

void dfs(int u) {
    // u节点已访问过，之所以需要vist[u]这样的状态数组，本质上是因为本题是一张图中多组欧拉回路，
    // 没跑过的点才需要当做起点跑欧拉回路，需要记录哪个跑过哪个没跑过
    vist[u] = 1;

    for (int i = h[u]; ~i; i = h[u]) { // 枚举u节点的每个出边i
        h[u] = ne[i];                  // 删边优化
        if (st[i]) continue;           // 此边访问过，不用再讨论,其实，这是在处理成对变换的另一边
        st[i] = st[i ^ 1] = 1;         // 无向图，成对标识已被访问过

        int v = e[i]; // 节点u通过边i指向点v
        dfs(v);       // 深搜v=e[i]这个点

        if (instk[v]) {                        // 如果v点在栈中，说明找到了行进路线中的环
            res[++rl].push_back(v);            // v记录到rl号环中
            while (stk.back() != v) {          // 一直把栈顶元素弹出，直到找出首次进入的那个v，也就是通过栈找环
                res[rl].push_back(stk.back()); // 将环中的节点记录到res[rl]这个结果集中去
                instk[stk.back()] = 0;         // 标识栈顶元素已出栈
                stk.pop_back();                // 栈顶元素出栈
            }
            res[rl].push_back(v); // 由于上面使用的是stk.back()!=v,这样是为了保持v还在栈中，让这个点重复命使用，可以参考图2的点3            
        } else {                  // 如果不在栈内
            stk.push_back(v);     // 入栈
            instk[v] = 1;         // 标识在栈内
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("P3520.in", "r", stdin);
#endif
    memset(h, -1, sizeof h); // 初始化链式前向星
    int n, m;
    scanf("%d %d", &n, &m); // n个顶点，m条边

    int a, b, s, t;
    while (m--) {
        scanf("%d %d %d %d", &a, &b, &s, &t); // a到b有一条边，颜色初始值是s,目标终止值是t
        if (s ^ t) {                          // 如果s与t不一样,建边。欧拉图需要每边只走一次
            add(a, b), add(b, a);             // 双向建边,因为可以正着走，也可以反着走，但正反边只能走1次
            d[a]++, d[b]++;                   // 维护度
        }
    }

    // 检查是否某个点的度是奇数，这样没有欧拉回路
    for (int i = 1; i <= n; i++)
        if (d[i] % 2) {
            puts("NIE");
            exit(0);
        }

    // 遍历每个节点
    for (int i = 1; i <= n; i++)
        if (!vist[i] && d[i]) { // 如果节点i没有访问过，并且，是数据中出现过的点，比如1，2，5，6出现，3，4不参加讨论问题
            dfs(i);             // 对节点i进行深搜，找简单环
            /*简单环分两种情况：
            ① 出发点在内的简单环
            ② 在行进路线上出现的简单环
            这两种情况处理办法不一样，需要分别对待，下面就是情况①
            由于上面已经通过一笔画的定理排除掉了非欧拉回路的可能，现在的图肯定是欧拉回路
            那么，在dfs过程中我们可以把路径上的环处理掉，那么，一定有从起点出发的环还在栈中，需要单独处理
            */
            res[++rl].push_back(i);
            while (stk.size()) {
                res[rl].push_back(stk.back());
                instk[stk.back()] = 0;
                stk.pop_back();
            }
        }

    // 输出环的数量
    printf("%d\n", rl);

    // 遍历每个环
    for (int i = 1; i <= rl; i++) {
        printf("%d ", res[i].size() - 1); // 输出环中节点个数，这里为什么要减1呢？因为是环嘛，首尾是一样的，加入了两次
        for (auto x : res[i]) printf("%d ", x);
        puts("");
    }
    return 0;
}
```

### 三、代码解析

先给出一组测试数据：
```cpp {.line-numbers}
20 23
7 3 0 1
3 2 1 0
5 6 1 1
6 4 1 0
4 1 0 1
2 5 0 1
7 4 0 0
1 7 0 1
7 6 1 1
3 5 1 0
3 6 0 1
17 8 0 0
8 16 1 1
19 18 0 0
18 1 1 1
18 20 1 1
20 19 1 1
9 10 1 1
10 13 0 0
13 14 0 1
14 9 0 1
9 15 0 0
9 13 0 1

```
![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/%7Byear%7D/%7Bmonth%7D/%7Bmd5%7D.%7BextName%7D/20230810114052.png)

我将按代码的执行流程来模拟一遍，可能挺长，耐心看完：

- 从$1$号点出发，因为$1-4$比$1-7$先给出，但由于 **链式前向星是头插法**，所以插入的在队头，所以先走$7$,也就是现在$1->7$的箭头方向
  
- $7->3$,由于$3->5$是先给出的数据，$3->6$是后给出的数据，所以产生两个分支，一个向$6$前进，另一个向$5$前进,(为啥不先跑$3->2$?是因为$3-2$先给出，头插法，所以先跑$5$)
- $2$准备走向$3$时，发现$3$已经在栈中了，也就是找到了一个简单环：将栈中元素准备弹出$2，5$  
- $Q:$为什么是$2,5$呢？$3$哪去了？**因为$3$不能出栈！**,原因很简单，这个点$3$除了在这个简单环以外，还在其它简单环中！如果我们把$3$也出了栈，后面的$1,7,3,6,4,1$中就没有了$3$, 那个就不是完整的简单环了！ 
- 那$3$不出栈，本简单环也不完整啊！是的，我们需要手动补上入口的$3$和出口的$3$
```cpp {.line-numbers}
res[++rl].push_back(v); //入口的3

while (stk.back() != v) { //将栈中不包含3的节点记录到路径中
    res[rl].push_back(stk.back());
    instk[stk.back()] = 0;        
    stk.pop_back();               
}

res[rl].push_back(v); //出口的3
``` 
- 继续行进，$3->6->4->1$,
然后$4$号节点，执行了下面的代码
```cpp {.line-numbers}
stk.push_back(v);     // 入栈
instk[v] = 1;         // 标识在栈内
```
将$1$号节点放入栈中。

至此，回到了$1$号节点，此时，由于$1$已经没有了出边，因为边都被我们删除掉了，可不没有了出边，递归终止了，没有机会将栈中存储的简单环路径：$7,3,6,4$保存成简单环！也就是在$dfs(1)$这样的起点后面，需要手动出栈，一出到底即可！不出干净还不行，会影响后面的其它环了~

```cpp {.line-numbers}
res[++rl].push_back(i);
while (stk.size()) {
    res[rl].push_back(stk.back());
    instk[stk.back()] = 0;
    stk.pop_back();
}            
```


### 四、并查集踩坑
我最开始错误的以为使用并查集一样可以完成任务，因为环嘛，当然是通过边相连的，如果用并查集维护，不就是可以找出哪些点通过边相连，而且，前面已经证明了存在欧拉回路，枚举每个家族的族长，以它为起点出发，不就可以找出所有环吗？

但事实证明我 **错的离谱**！原因是题目要求找出的是 **简单环**$Simple \  Circle$！比如下面的数据样例直接教你做人（参考下图中右侧部分）！我的答案就会把左边的那一大堆认为是一个环，可人家答案要求的是多个简单环，也就是：
```cpp {.line-numbers}
3
3 3 5 2 3 
5 1 7 3 6 4 1 
3 9 13 14 9 
```
我的答案是这样滴：
```cpp {.line-numbers}
2
7 6 4 1 7 3 2 5 3 6 
3 13 14 9 13 
```
这不是简单环，违背了原则：**除起点外，其它点出现$1$次**。
节点$3$出现了两次，节点$6$出现了两次，是标准错误答案。

#### 结论
<font color='red' size=4><b>这种找简单环，只能是用$dfs$，不能用并查集</b></font>

![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/%7Byear%7D/%7Bmonth%7D/%7Bmd5%7D.%7BextName%7D/20230810085346.png)


#### 标准错误并查集答案
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10, M = 2e6 + 10;

// 标准错误答案@！
// #2162. 「POI2011 R2 Day1」垃圾运输 Garbage
// https://loj.ac/s/1857935

// 并查集
int p[N], sz[N];
int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int d[N];

vector<int> res[N];
int rl;

int st[M];

void dfs(int u) {
    for (int i = h[u]; ~i; i = h[u]) {
        h[u] = ne[i];
        if (st[i]) continue;
        st[i] = st[i ^ 1] = 1;
        int v = e[i];
        dfs(v);
        cout << u << " ";
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("P3520.in", "r", stdin);
#endif
    memset(h, -1, sizeof h);
    int n, m;
    scanf("%d %d", &n, &m);

    // 初始化并查集
    for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;

    int a, b, s, t;
    while (m--) {
        scanf("%d %d %d %d", &a, &b, &s, &t);
        if (s ^ t) {
            add(a, b), add(b, a);
            d[a]++, d[b]++;
            // 并查集
            int pa = find(a), pb = find(b);
            if (pa != pb) {
                p[pb] = pa;
                sz[pa] += sz[pb]; // 维护家庭人员数量
            }
        }
    }

    for (int i = 1; i <= n; i++)
        if (d[i] % 2) {
            puts("NIE");
            exit(0);
        }

    // 肯定是存在欧拉回路,现在是几个环呢？可以用并查集提前处理出来

    // 从头到尾，看一下有多少个家庭，就是有多少个环
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (d[i] && i == p[i]) cnt++;
    cout << cnt << endl;

    for (int i = 1; i <= n; i++)
        if (d[i] && i == p[i]) {
            cout << sz[i] << " " << i << " ";
            dfs(i);
            cout << endl;
        }
    return 0;
}
```