ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2132. Graph Decomposition. Version 2

Hint
Posted by Mickkie 29 May 2020 00:50
This problem is easier than rating should be if you know the trick.

Invariant: graph G is decomposable if and only if all the connected components of G has even number of edges.

A tree is very easy to be decomposed. Creating a tree equivalent to each connected component will lead to the answer.

Hope this help, Mick :)
Re: Hint
Posted by bsu.mmf.team 30 Dec 2020 19:37
It helped me a lot, thank you!
I read a proof of the fact that any connected graph with even number of edges is decomposable, but it was quite complicated and didn't allude at any good algorithm underneath.
Your idea is much simpler and easier to proof