资源描述：
《算法习题解答(二)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Homework6Solutions1.22.2-6(pg.539)Therearetwotypesofprofessionalwrestlers:goodguys,andbadguys.Betweenanypairofprofessionalwrestlers,theremayormaynotbearivalry.Supposethatwehavenprofessionalwrestlersandwehavealistofrpairsofwrestlersforwhichtherearerivalrie
2、s.GiveanO(n+r)-timealgorithmthatdetermineswhetheritispossibletodesignatesomeofthewrestlersasgoodguysandtheremainderasbadguyssuchthateachrivalryisbetweenagoodguyandabadguy.Ifitispossibletoperformsuchadesignationyouralgorithmshouldproduceit.Assumptions:1.Ar
3、ivalry(A,B)representsthefactthatAhasarivalrywithB.ItdoesnotspecifywhetherornotAorBisthegoodorbadguy.2.Somewrestlersmaynotbeinvolvedinrivalries.Thesewrestlersareneithergoodguysnorbadguys.Thealgorithmisnotconcernedwiththem.3.Anypossiblesolutionofgoodguysand
4、badguysisacceptable.Forexample,considerthefollowingsetup:Wrestlers={A,B,C,D,E},Rivalries={(A,B),(B,C),(D,E)}Therearefourpossiblesolutionsforthissetup:1.Goodguys={A,C,D},Badguys={B,E}2.Goodguys={A,C,E},Badguys=(B,D}3.Goodguys={B,E},Badguys={A,C,D}4.Goodguy
5、s={B,D},Badguys={A,C,E}Ancorrectalgorithmcouldreturnanyoneofthesesolutions.Setup:Werepresenttherivalriesasagraph,G=(V,E).Theverticesarethewrestlers,andtheedgesaretherivalries.Therefore,
6、V
7、=n,and
8、E
9、=r.Algorithm:1.Discardallverticesofdegree0.Thesearewrestle
10、rswhohavenorivalries.Wearenotconcernedwiththem.2.Separateallconnectedcomponentsoftheremaininggraph.Processeachcomponentindividuallyinthefollowingsteps.3.LetC=(Vc,Ec)betheconnectedcomponent.Chooseonevertexratrandom(ordeterministically-itdoesn’tmatter)fromV
11、c.Withoutlossofgenerality(remember,anypossiblesolution,iscorrect),letrbeclassifiedasaGoodguy.4.Runamodifiedbreadth-firstsearchfromtheroot.Insteadofmaintainingd[]andf[]arrays,savethepath-lengthfromeachvertextor.AllverticeswithoddpathlengthstorareBadguys;al
12、lverticeswithevenpathlengthstorareGoodguys.5.ExamineeveryedgeinEc.Iftheedgeisbetweentwoverticeswhosepathlengthstorarebothevenorbothodd,thenwehaveestablishedarivalrybetweentwoGoodorBadguys.Ifthisisthecase,wereturnfal
