Signed graph P38073
An undirected graph is signed if each edge has a positive or negative sign. A signed graph is called balanced if the product of all signs around every cycle is positive.
Given a signed graph, can you tell if it is balanced or not?
Input
Input consists of several cases, each one with the number of vertices n, followed by the number of edges m, followed by m triples x y s to indicate an edge between x and y with sign s ∈ { −1, 1 }. Assume 1 ≤ n ≤ 105, 0 ≤ m ≤ 5n, that vertices are numbered between 0 and n−1, x ≠ y, and that there is no more than one edge between x and y.
Output
For every graph, print “yes” if it is balanced; otherwise print “no”.
Public test cases
Input
7 5 0 1 1 1 2 -1 1 4 1 2 4 -1 6 5 -1 3 3 0 1 -1 2 0 -1 2 1 -1
Output
yes no
Information
- Author
- Conrado Martínez
- Language
- English
- Official solutions
- C++
- User solutions
- C++