How to solve this adhoc task?
You are given an undirected graph with $$$N$$$ vertexes and $$$M$$$ edges. Each vertex $$$i$$$ has a value, $$$a[i]$$$.
Is is possible to make all vertexes have the same value, using the following operation multiple times (or not use it at all):
- If there is a vertex $$$u$$$, such that vertexes $$$v$$$ and $$$w$$$ are directly connected to it, then change $$$a[v]$$$, $$$a[w]$$$ to $$$a[v] + k$$$ and $$$a[w] + k$$$ respectively, where $$$k$$$ is any integer.
If it is possible, print "YES", else "NO".
$$$N$$$ <= 100000, $$$M$$$ <= 200000
Link: https://www.acmicpc.net/problem/30187
I have been thinking in direction that if it is not a bipartite graph, then answer is YES. No idea is that even right or not.
Auto comment: topic has been updated by pure_mem (previous revision, new revision, compare).
Auto comment: topic has been updated by pure_mem (previous revision, new revision, compare).
Note that the operation doesn't change the parity of sum of values on a connected component. Iterate over each connected component $$$C$$$. Let $$$size(C)$$$ be the number of vertices in $$$C$$$ and $$$sum(C)$$$ the sum of values of all vertices in $$$C$$$. We now do bunch of caseworks.
(1) $$$C$$$ is non-bipartite.
(1-1) $$$size(C)$$$ is even.
(1-2) $$$size(C)$$$ is odd.
(2) $$$C$$$ is bipartite.
(2-1) $$$size(C)=1$$$
(2-2) $$$size(C)\ge 2$$$
(2-2-1) $$$Q$$$ has a vertex with degree $$$\ge 3$$$ (in the original graph).
(2-2-2) All the vertices of $$$Q$$$ has degree $$$\le 2$$$ (in the original graph).
(2-2-2-1) $$$G(P)$$$ is non-bipartite.
(2-2-2-2) $$$G(P)$$$ is bipartite.
(2-2-2-2-1) $$$size(L) = size(R)$$$.
(2-2-2-2-2) $$$size(L) \ne size(R)$$$.
Finally, check if all the forcings are consistent. If they are contradictory, print "NO". Otherwise, we've checked for each connected component that all the forced values are possibles, so print "YES".