网上找一些试题题解jobbery解题报告

《Jobbery》题目出自Ural1198题目出自Ural1198——广东省韶关市第一中学刘家骅题目描述：HardtimescameforMartiansenate.EventhisprideofMartiandemocracycannotopposethealmightyjobbery.Let'sconsidertheprocedureoftypicaldecisionmaking.AmemberofMartiansenate,whoneedsacertainlaw,submitsittosenate.Toimprovehischancesthatlawisaccepted,hemakesaphonecalltoeachofsenatemembersonwhomhehasthegoodsinhissafe.Thenhekindlysuggeststothosesenatorstosupportthenewlaw.Moreover,toavoidoccasionalrejectionofthisimportantlaw,heaskseachofthemtomakethesameprocedurewiththeirsafes.Andeachofthemhavingnochoicemakesasimilarrangeofphonecallstothoseonwhome,inturn,hehasthegoods.Ifeverysenatorsupportsthenewlawthepresidenthasnothingtodobuttoapproveit.Otherwisehecanrejectitandsendbacktosenateforlawimprovements.Itisevident,thatjustelectedpresidentHonestmandislikessuchsituation.Sohestartstostruggleagainstthejobbery.Andfirstofallhewantstoputtojailthemostdangeroussenatemembers.Anddefinitely,ifsenatorisabletomakeeventheharmfullawapproved,heisadangerousone.SosecretserviceofMartianpresidenthasalreadycheckedsafesofeachsenatemember,andfoundoutonwhomeachofthemhasthegoods.Martianpresidentknowsaboutyourachievementsinprogrammingandheasksyoupersonallyforahelp.InputThefirstlineofinputcontainssingleintegerN—thenumberofsenatemembers(1<=N<=2000).Eachsenatememberisuniquelyidentifiedwithanumberfrom1toN.EachofsubsequentNlinescontainsinformationaboutsenatemembers.Thei-thlinecontainslistofsenatemembers(givenbynumericidentifiers)onwhomehehasthegoods.Lististerminatedbynumber0.OutputPrintthelistofidentifiersofalldangeroussenatemembersinasingleline.Thenumbersinthelistmustbepresentinincreasingorder.Thelistmustbeterminatedbynumber0.SampleInput5320045015020SampleOutput1340题目分析：题目大意是有N个点，点之间有一些有向边，问有多少个点满足条件：从这个点出发能够到达图中其他所有点。很容易想到最简单的算法——广度搜索（BFS）。但是BFS一次的时间复杂度为O（N2），那么总的时间复杂度为O（N3），对于N=2000的数据规模显然过大了。改进算法明显需要利用图论知识——对于这样一个有向图，我们可以进行重构，将图中的每个极大强连通分量合并成一个点。（找有向图中的极大强连通分量参见《算法艺术与信息学竞赛》P286）然后再在新图里进行BFS，在新图里能够到达其他所有点的点所代表的原图中的强连通分量里的所有点，都满足题目条件。这种算法显然比原来的算法要快，但是考虑到原图中可合并的点不多但有向边不少的极限数据，这种算法的速度依然不能令人满意。在对原图进行合并后，若新图不连通，显然不存在满足题目条件的点。当新图连通时，认真思考可以得出这样一个结论：当且仅当新图中有且只有一个点的入度为零时存在满足题目条件的点，即为这个入度为零的点。我们可以简略证明一下：在新图中从其中任意入度不为零的点出发，逆有向边方向前进，可以得到一个点的序列X1、X2、X3…由于新图中不存在圈，所以每个点只能出现一次，若不存在入度为零的点，那么序列的长度为无限大，这与点的个数有限且每个点只出现一次矛盾，所以新图中必然存在入度为零的点。若新图中只存在一个入度为零的点P，那么序列只有到P时才可能停止，若序列中没有点P，则序列的长度为无穷大，与点的个数有限且每个点只出现一次矛盾，所以序列必须包括点P，则从P点出发一定能到达任意其他点，所以P点即为满足题目条件的点；当新图中存在不只一个入度为零的点时，图中入度不为零的点显然无法到达这些入度为零的点，而这些入度为零的点中的任一个也无法到达其他入度为零的点，所以不存在能够到达图中