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): <br>↵
- 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.
↵
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): <br>↵
- 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.
