Need help with another graph theory problem

Revision en3, by xuanquang1999, 2017-07-06 17:57:13

In this morning training, our team was given this problem from Prologin contest — 2015 Regional event (unfortunately, the statement is written in French, but I'll try to summarize the statement as accurate as possible):

"There are N rooms and M roads, road i directly connect room ui with room vi. There are also K switches, switch i can control road ai and road bi. More specifically, if switch i is on, roads ai is enabled and roads bi is disabled, and vice-versa (disabled road can't be walked on). If there is no switch controlling road i, then that road is always enabled. It's guaranteed that one road will be controlled by at most one switch, and when all switches are off, the roads system will form a tree (connected acyclic graph). Is it true that for all 2k states of the switches, the roads system will always form a tree?"

Our teams have discussed this problem for the entire morning but failed to come up with any algorithm that can solve this problem in polynomial time. It also doesn't help that the original statement didn't give constraint of N, M, and K, too. Can someone help us on this matter? Thanks in advance.

Tags graph, help needed


  Rev. Lang. By When Δ Comment
en3 English xuanquang1999 2017-07-06 17:57:13 6
en2 English xuanquang1999 2017-07-06 17:56:40 4 Tiny change: 'l road $a_i$ and road $b_i$. More sp' -> 'l road $a_j$ and road $b_j$. More sp'
en1 English xuanquang1999 2017-07-06 17:55:35 1295 Initial revision (published)