Marco_L_T's blog

By Marco_L_T, 3 years ago, In English,

I've been working on a problem on graph,but can't come up with a solution of it.

Here is the problem.

John has N (N<=10000) dogs.Now they're going to cross a river.However,there's only a boat that can only carry one person and one dog each time.However,some of the dogs hate the others so much that they'll fight if John isn't around them. M (M<=25000) constraints describe the situation.Each is described as (x,y,z),which means the dogs with numbers x,y,z will fight with each other if John is away.But they won't fight if one of them is at the opposite bank with the other two.

Now you are asked to determine whether there is a way to send all the dogs to the other bank of the river without fighting.You don't need to print the detailed method,which means you just need to print "yes" or "no".Remember John must be on the boat and the boat can only carry one dog each time.

Input:

On the first line , two numbers N and M.

From the second to the (M+1)th line,each line has three numbers (x,y,z),which describe a constraint.

Output:

A single line,containing "yes" or "no"

Sample Input 1:

6 9

1 2 3

1 2 4

1 2 5

1 2 6

1 3 6

1 4 6

1 5 6

1 3 4

1 4 5

Sample Output 1:

yes

Sample Input 2:

6 10

1 2 3

1 2 4

1 2 5

1 2 6

1 3 6

1 4 6

1 5 6

1 3 4

1 3 5

1 4 5

Sample Output 2:

no

I translate the problem on my own.Sorry for my poor English.

Can anyone tell me the solution to the problem? Thanks a lot!

 
 
 
 
  • Vote: I like it
  • +19
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone give me a response? I'm really eager to solve the problem!