You are not logged in. Please login at www.codechef.com to post your questions!

×

spoj buglife problem

i am not able to understand the problem can somebody explain me the question in proper way. the link of question is http://www.spoj.com/problems/BUGLIFE/ thanks a lot in advance.

asked 23 Jan '16, 17:54

rahulsup's gravatar image

1★rahulsup
251211
accept rate: 0%


-1

is this problem, you have to check if the graph is bipartite or not, and that is all.

If it is, answer is "no suspicious activity", else the answer is the opposite.

The meaning of a bipartite graph -> GeeksForGeeks

to check it, just run a standard BFS.

label the source node(1st bug in this case) as 1, all the other nodes adjacent to it as 0, then all the others adjacent to these ones as 1 and so on...

each node should have the label "1-x" if x is the label of the parent of the node.

if at anytime, you encounter a node that has already been labelled, and its label does not match the one that you were going to assign it, then the answer is "suspicious activity found".

link

answered 23 Jan '16, 18:57

tanmay_sachan's gravatar image

1★tanmay_sachan
424
accept rate: 9%

(23 Jan '16, 19:26) rahulsup1★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,115

question asked: 23 Jan '16, 17:54

question was seen: 425 times

last updated: 23 Jan '16, 19:26