Boomerangs (Problem K, 2018 ICPC Asia Jakarta Regional Contest, 2018)
Time limit: 0.5 sec
Memory limit: 256MB
Author: Ivan Adrian Koswara

# Problem Statement

Let $G = (V, E)$ be a simple undirected graph with $N$ vertices and $M$ edges, where $V = \{1, \ldots, N\}$. A tuple $\langle u, v, w \rangle$ is called as boomerang in $G$ if and only if $\{(u, v), (v, w)\} \subseteq E$ and $u \ne w$; in other words, a boomerang consists of two edges which share a common vertex.

Given $G$, your task is to find as many disjoint boomerangs as possible in $G$. A set $S$ contains disjoint boomerangs if and only if each edge in $G$ only appears at most once (in one boomerang) in $S$. You may output any valid disjoint boomerangs, but the number of disjoint boomerangs should be maximum.

For example, consider a graph $G = (V, E)$ of $N = 5$ vertices and $M = 7$ edges where $E = \{(1, 2), (1, 4), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5)\}$.

![IMAGE](icpc-jakarta-2018-boomerang-1.png)

The maximum number of disjoint boomerangs in this example graph is $3$. One example set containing the $3$ disjoint boomerangs is $\{\langle 4, 1, 2 \rangle, \langle 4, 3, 2 \rangle, \langle 2, 5, 3 \rangle\}$; no set can contain more than $3$ disjoint boomerangs in this example.

# Input

Input begins with a line containing two integers: $N\ M$ $(1 \leq N, M \leq 100000)$, representing the number of vertices and the number edges in $G$, respectively. The next $M$ lines, each contains two integers: $u_i\ v_i$ $(1 \leq u_i < v_i \leq N)$, representing the edge $(u_i, v_i)$ in $G$. You may safely assume that each edge appears at most once in the given list.

# Output

The first line of output contains an integer: $K$, representing the maximum number of disjoint boomerangs in $G$. The next $K$ lines, each contains three integers: $u\ v\ w$ (each separated by a single space), representing a boomerang $\langle u, v, w \rangle$. All boomerangs in the output should be disjoint. If there is more than one valid solution, you can output any of them.

# Sample Input #1
```
5 7
1 2
1 4
2 3
2 4
2 5
3 4
3 5
```
# Sample Output #1
```
3
4 1 2
4 3 2
2 5 3
```
# Sample Input #2
```
4 6
1 2
1 3
1 4
2 3
2 4
3 4
```
# Sample Output #2
```
3
1 2 3
1 3 4
1 4 2
```
# Sample Input #3
```
3 3
1 2
1 3
2 3
```
# Sample Output #3
```
1
2 1 3
```

Sample inputs:
5 7
1 2
1 4
2 3
2 4
2 5
3 4
3 5

4 6
1 2
1 3
1 4
2 3
2 4
3 4

3 3
1 2
1 3
2 3

Sample outputs:
3
4 1 2
4 3 2
2 5 3

3
1 2 3
1 3 4
1 4 2

1
2 1 3

# Solution Analysis
Analysis author: Jonathan Irvin Gunawan

If the graph is not connected, we can run the boomerang partition algorithm independently for each of the connected components. Therefore, the rest of the discussion assumes that the graph is connected.

For now, assume that the graph has even number of edges. Since the boomerangs must be disjoint, and each boomerang uses two edges, there are at most $\left\lfloor \frac{|E|}{2} \right\rfloor$ boomerangs that we can find. It turns out that we can find $\left\lfloor \frac{|E|}{2} \right\rfloor$ boomerangs (i.e. a partition of boomerangs), thus finding the optimal number of boomerangs.

We can prove this by induction. If we have a connected graph with 2 edges, we can obviously find a partition of boomerangs. Also, we will prove that we can find a partition of boomerangs on a connected graph with $x$ (even) edges if we can find a partition of boomerangs on a connected graph with $y$ (even) edges for all $y < x$.

Suppose we have a connected graph $G$ with an even number of edges. There are two cases:

- Suppose there is no bridge in $G$. We can always find a boomerang in $G$ where removing the boomerang edges in $G$ causes either $G$ to remain connected, or to be separated into two connected components, each having an even number of edges.

- Suppose there is a bridge $(u, v)$ in $G$. Let $U$ and $V$ be the two connected components if we remove the edge $u, v$, with $u$ in $U$ and $v$ in $V$. Since $G$ has even number of edges, exactly one of $U$ or $V$ must have an even number of edges. Without loss of generality, suppose $U$ has an even number of edges. We can choose a node $w$ in $V$ such that removing the edge $(v, w)$ causes $V$ to remain a connected component, or $V$ to be separated into two connected components, each having an even number of edges.

In both cases, we can find one boomerang, and removing them from $G$ may cause $G$ to be separated into several connected components. However, since we can find a partition of boomerangs in each of the connected components, we can find a partition of boomerangs in $G$.

Implementing the induction above using recursion is tricky—we need a data structure that returns a bridge in an online manner. Fortunately, there is a simpler algorithm. To make the discussion easier, we will first find a partition of boomerangs on a tree with an even number of edges.

Let $T$ be a tree with an even number of edges. While there is an edge on $T$, we do the following:

- Suppose there is a node $u$ having two children $v$ and $w$ which are leaves. We can create a boomerang $(v, u, w)$ and remove these edges.

- Otherwise, we can always find a node $u$ with only one child, and that one child is a leaf. We can create a boomerang $(child(u), u, parent(u))$ and remove these edges.

Since the rest of the tree is still connected, we can still find a partition of boomerangs. We can implement this in $O(N)$ time using DFS.

We can convert the original graph $G$ into a tree while keeping the number of edges by adding the edge in $G$ one by one. If adding an edge $(u, v)$ creates a cycle, we add an edge $(u, w)$ instead, where $w$ is a new node. However, when we print the solutions, keep in mind that $w$'s original ID is actually $v$. This algorithm runs in $O(N \log N)$.

The last piece of the puzzle is to figure out what to do if we have an odd number of edges. We can simply discard any one of them, since an additional one edge is not enough to create another boomerang.

Special judge (C++ scorer):
#include <bits/stdc++.h>
using namespace std;

int wa(int status = 0) {
  cout << "WA" << endl;
  cerr << status << endl;
  return 0;
}

int ac() {
  cout << "AC" << endl;
  return 0;
}

int checks(istream& tc_in, istream& tc_out, istream& con_out) {
  int N, M;
  tc_in >> N >> M;
  vector<int> U(M), V(M);

  set<pair<int, int>> edges;

  for (int i = 0; i < M; ++i) {
    tc_in >> U[i] >> V[i];
    edges.insert(make_pair(U[i], V[i]));
    edges.insert(make_pair(V[i], U[i]));
  }

  int O_out, O_con;
  tc_out >> O_out;

  if (!(con_out >> O_con)) {
    return wa(1);
  }

  if (O_out != O_con) {
    return wa(2);
  }

  for (int i = 0; i < O_con; ++i) {
    int A, B, C;
    if (!(con_out >> A >> B >> C)) {
      return wa(3);
    }
    if (A == C) {
      return wa(4);
    }
    if (edges.count(make_pair(A, B)) && edges.count(make_pair(B, C))) {
      edges.erase(make_pair(A, B));
      edges.erase(make_pair(B, A));
      edges.erase(make_pair(B, C));
      edges.erase(make_pair(C, B));
    } else {
      return wa(5);
    }
  }

  if (con_out >> O_con) {
    return wa(6);
  }

  return ac();
}

int main(int argc, char* argv[]) {
  ifstream tc_in(argv[1]);
  ifstream tc_out(argv[2]);
  ifstream con_out(argv[3]);

  return checks(strcmp(argv[1], "-") == 0 ? cin : tc_in,
                strcmp(argv[2], "-") == 0 ? cin : tc_out,
                strcmp(argv[3], "-") == 0 ? cin : con_out);
}