CF405E Graph Cutting 解题报告

CF405E Graph Cutting 解题报告

1 题目链接

https://codeforces.com/problemset/problem/405/E

2 题目整理

题目 ： 图形切割

题目描述

小克里斯正在参加一场图形切割比赛。 他是一个职业选手。 是时候充分考验他的技能了。

给出了一个简单的无向连通图，它有$n$个顶点(编号从$1$到$n$)和$m$条边，每条边长度为$1$。 问题是把它切成$\frac{m}{2}$个长度为$2$的路径。 形式上，克里斯必须把图的所有边分成成对的这样，一对中的边是相邻的，每条边必须恰好包含在一对中。

你有机会和克里斯竞争。 找到一种方法来切割给定的图表或确定它是不可能的!

输入格式

第一行两个整数$n,m$，分别表示顶点的个数与边的个数。

接下来$m$行每行两个整数$u_i,v_i$，分别表示第$i$条无向边的两个端点。

输出格式

如果这个图有可能被切分，输出$\frac{m}{2}$行，每行三个数$abc$，分别表示一组长度为2的路径中按遍历顺序输出的三个点的编号，如果存在多种切分方式，输出任意一种即可。

否则，输出一行一个字符串$"Nosolution"$。

样例输入1

8 12
1 2
2 3
3 4
4 1
1 3
2 4
3 5
3 6
5 6
6 7
6 8
7 8

样例输出1

1 2 4
1 3 2
1 4 3
5 3 6
5 6 8
6 7 8

样例输入2

3 3
1 2
2 3
3 1

样例输出2

No solution

样例输入3

3 2
1 2
2 3

样例输出3

1 2 3

数据范围

对于$100\%$的数据:

• $1\le n,m\le 10^5$
• $1\le u_i,v_i\le n$
• $u_i?=v_i$

3 题意分析

3.1 题目大意

给你一个$n$个点$m$条边的简单无向图，问你能否将这个图分割成$\frac{m}{2}$个长度恰好为$2$的路径，使得每条边都恰好出现一次。如果能，请输出其中一种构造，否则输出$"Nosolution"$。

3.2 样例分析

如上所述。

4 解法分析

一道dfs树 + 构造的神题（可能是因为我太水了）。

我们先考虑一棵树的情况。

如果题目给的是一棵树的话，若我们现在已经来到了结点$root$,那么我们先把他的儿子顶点先递归一遍，然后再来判断他的儿子节点。假设现在他正在判断儿子节点$v_i$：

• 如果此儿子节点递归构造后还有剩余的边和点$c$没有用到，那么我们就将$root{v}_{i}c$构成一组即可。
• 如果此儿子节点没有剩余的边，那么把所有这样的儿子节点(假设总共有$p$个)$v_i$放进一个数组里$d_1,d_2,?,d_p$,然后将$d_{1}root{d}_2$构成一组，$d_{3}root{d}_4$构成一组，$?$,一直下去。这里，如果$p$为奇数，则把$d_p$看做未构造的顶点，供前面的递归使用。

这里可以发现，只要$m$是偶数，就一定能构造出来；只要$m$是奇数，就一定无法构造。

那对于图来说呢，当然我们可以通过dfs，把这个图转化成一颗树。

这样，这道题就完成了。(真的没想到这篇博客写的这么累)

AC代码

ACCode #001

// From ko_osaga
// Rating 3276
// reason : 思路清晰代码简洁明了，运用了set来储存图（怎么感觉\ 有点浪费？）
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
typedef vector<int> vi;set<int> gph[100005];
int n, m;int dfs(int x){
    vector<int> lis;while(gph[x].size()){
    int p = *gph[x].begin();gph[x].erase(p);gph[p].erase(x);int t = dfs(p);if(t != -1){
    printf("%d %d %d\n", x, p, t);}else{
    lis.push_back(p);}}for(int i=lis.size()%2; i<lis.size(); i+=2){
    printf("%d %d %d\n",lis[i], x, lis[i+1]);}if(lis.size() & 1) return lis[0];return -1;
}
int main(){
    scanf("%d %d",&n,&m);if(m%2 == 1){
    puts("No solution");return 0;}for(int i=0; i<m; i++){
    int s, e;scanf("%d %d",&s,&e);gph[s].insert(e);gph[e].insert(s);}dfs(1);
}

ACCode #002

// From RNS_MHB
// Rating 2539
// reason : 思路清晰代码简洁明了，先建立dfs树，然后再跑构造的。
#include <stdio.h>
#include <vector>
#include <memory.h>
#include <algorithm>
#define N 100100
#define clr(a) memset(a, 0, sizeof(a))using namespace std;int head[N], to[N<<1], next[N<<1];
int n, m;
vector <int> vec[N];
bool vis[N];
int p[N];
bool chk[N];
int dep[N];
int id[N];
int linkp[N];bool cmp(int x, int y) {
    return dep[x]>dep[y];
}inline int exc(int v) {
    if (v>m) return v-m;return v;
}void dfs(int u) {
    int i, j, k;vis[u]=1, id[u]=u;dep[u]=dep[p[u]]+1;for (i=head[u]; i; i=next[i]) {
    j=to[i];if (p[u]==j) continue;k=exc(i);if (!chk[k]) {
    vec[u].push_back(j);chk[k]=1;}if (!vis[j]) p[j]=u, dfs(j);}
}int main() {
    int i, j, k, I;bool state;
// freopen ("in.txt", "r", stdin);scanf("%d %d", &n, &m);for (i=1; i<=m; i++) {
    scanf("%d %d", &j, &k);to[i]=k, next[i]=head[j], head[j]=i;to[i+m]=j, next[i+m]=head[k], head[k]=i+m;}if (m&1) {
    puts("No solution");return 0;}dfs(1);sort(id+1, id+n+1, cmp);for (I=1; I<=n; I++) {
    i=id[I];state=0;for (j=0; j<vec[i].size(); j++) {
    k=vec[i][j];if (p[k]==i && linkp[k]) continue;if (!state) printf("%d %d ", k, i);else printf("%d\n", k);if (p[k]==i) linkp[k]=1;state^=1;}if (state) {
    linkp[i]=1;printf("%d\n", p[i]);}}return 0;
}

ACCode #003

// From vepifanov
// Rating 2970
// reason : 思路清晰代码简洁明了
#include <cstdio>
#include <numeric>
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <queue>
#include <sstream>
#include <deque>using namespace std;#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i = 0; i < (n); i++)
#define re return
#define fi first
#define se second
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define sqr(x) ((x) * (x))
#define sqrt(x) sqrt(abs(x))
#define y0 y3487465
#define y1 y8687969
#define fill(x,y) memset(x,y,sizeof(x))typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef double D;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef vector<vi> vvi;template<class T> T abs(T x) {
     re x > 0 ? x : -x; }int n;
int m;
vi v[100000];
int was[100000];
vector<pair<int, ii> > res;int go (int x, int p) {
    vi u;was[x] = 1;for (int i = 0; i < sz (v[x]); i++) {
    int y = v[x][i], z;if (y == p) continue;if (!was[y]) {
    z = go (y, x);if (z != -1) res.pb (mp (z, mp (y, x))); else u.pb (y);} elseif (was[y] == 2) u.pb (y);}while (sz (u) > 1) {
    int a = u.back ();u.pop_back ();int b = u.back ();u.pop_back ();res.pb (mp (a, mp (x, b)));}was[x] = 2;if (u.empty ()) re -1;re u[0];
}int main () {
    scanf ("%d%d", &n, &m);for (int i = 0; i < m; i++) {
    int a, b;scanf ("%d%d", &a, &b); a--; b--;v[a].pb (b);v[b].pb (a);}for (int i = 0; i < n; i++)if (!was[i] && go (i, i) != -1) {
    printf ("No solution\n");re 0;}for (int i = 0; i < m / 2; i++)printf ("%d %d %d\n", res[i].fi + 1, res[i].se.fi + 1, res[i].se.se + 1);return 0;
}