|
|
#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
|
|
|
|
|
|
// cout << "u=" << u << ",v=" << v << ",instk[1]=" << instk[1] << endl;
|
|
|
/*
|
|
|
u=1,v=7,instk[1]=0
|
|
|
u=7,v=3,instk[1]=0
|
|
|
u=3,v=6,instk[1]=0
|
|
|
u=6,v=4,instk[1]=0
|
|
|
u=4,v=1,instk[1]=0
|
|
|
u=3,v=5,instk[1]=1
|
|
|
u=5,v=2,instk[1]=1
|
|
|
u=2,v=3,instk[1]=1
|
|
|
u=9,v=13,instk[1]=0
|
|
|
u=13,v=14,instk[1]=0
|
|
|
u=14,v=9,instk[1]=0
|
|
|
*/
|
|
|
// 代码跟踪表示，现在黄海画的图节点走向是正确的
|
|
|
|
|
|
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;
|
|
|
} |
