Check to see whether all bottles can be closed

This is a discussion on Check to see whether all bottles can be closed within the C++ Programming forums, part of the General Programming Boards category; The picture shows the relation between lids and bottles. If there is an edge between a lid and a bottle ...

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    50

    Check to see whether all bottles can be closed

    The picture shows the relation between lids and bottles. If there is an edge between a lid and a bottle that means that that bottlle can be closed with that lid

    How can i say that all bottles can be closed with lids using a graph traversal method?
    Attached Images Attached Images  

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Looks like the marriage/perfect matching problem.

  3. #3
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    yeah what traversal algorithm should i use to prove this?

  4. #4
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    since graph is bipartite by definition, can you just show that graph is connected?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BN_CLICKED, change button style
    By bennyandthejets in forum Windows Programming
    Replies: 13
    Last Post: 07-06-2010, 12:42 AM
  2. How can i check a directory for certain files?
    By patrioticpar883 in forum C++ Programming
    Replies: 13
    Last Post: 02-01-2008, 05:27 PM
  3. how to check input is decimal or not?
    By kalamram in forum C Programming
    Replies: 3
    Last Post: 08-31-2007, 08:07 PM
  4. Please check this loop
    By Daesom in forum C++ Programming
    Replies: 13
    Last Post: 11-02-2006, 01:52 AM
  5. check my code ( if statement, file existance )
    By Shadow in forum C Programming
    Replies: 1
    Last Post: 10-04-2001, 12:13 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21