Algorithm --> 树中求顶点A和B共同祖先

树中求顶点A和B共同祖先

题目:

  给定一颗树,以及两个顶点A和B,求最近的共同祖先,和包含的子顶点个数?

比如:给定如下图的树,以及顶点13和8,则共同祖先为3,以3为root的子顶点共有8个

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAeUAAAFBCAIAAADG3yDNAAAgAElEQVR4nO3d7U8bWb4ncP9Z0UqbF7ti36BIy4tZ7uzccLdzfQNyo1mclSDaNbrysuNZHsSYTJs7NuwaputeF+1pe4VpmnXW7jbyxQhMeLDaUYwgBm6cWAZSE9uJyxbyvqgZD+HB1NNx1Sl/P8oLhsH1QFPfOvU759Qx1QEAgAYmrQ8AAABEQV4DANABeQ0AQAfkNQAAHZDXAAB0QF4DANABeQ0AQAfkNQAAHZDXAAB0QF4DANABeQ0AQAfkNQAAHZDXAAB0QF4DANABeQ0AQAfkNQAAHZDXAAB0QF4DANABeQ2tc8qVttLHjX/FckXrIwKgCfIayMoVuEBke8gZvPdwrLPfZXGwjX8dvVP3H00OOYNLq6lTrqT1kQLoHfIaSMkVuGFXqMvqHvWGY8nMjT/DV2uxZGbEs9zZ7xr1hpHaAE0gr0F9fLXmZKLdg7PhRFr8pwKR7S6reyYQJ3dgAFRDXoPKTrmSxcGyK5t8tSb1s3y1NhOIWxwsStsA1yGvQU2ZbN5sZ1L7b5RsZCt9bLYzuQKn1lEBGAPyGlSTK3A9tjlVcjabO7M4WEQ2wGXIa1BHsVwx25ls7kytDQpNdRlFFQCjQl6DOgbG/YndQ3W3GUtmhpxBdbcJQC/kNahgaTU14lkmseUhZ/C2sYAA7QZ5DUrx1VqX1U1o6HQ2d9Zjm0NVBKCOvAbl2JVNJxMlt30nE2VXNsltH4AWyGtQqsvqJjqQI7X/xmxnyG0fgBbIa1AkmzvrHpwlvZfOfhemqgMgr0GR+dD69EJM5A/n8/nFxcW+vj6pexnxLC+tpqR+CsBgkNegyLArJP4lIRMTE0dHRyaT5L86cuNPACiCvAZFZMw+l5HXid3DgXG/1E8BGAzyGhSR0dkoI68z2XyPbU7qpwAMBnkNitx7OCb1IzLyOlfguqxuqZ8CMBjkNSgiY+SGjLxuzSgUAJ1DXoMiralfb6WPLQ5W6qcADAZ5DYrIeL8HxocAyIO8BkVmAnHxK3iZPid+L5iSDlBHXoNCrRm5QXrKOwAVkNegFOkwRWcjgAB5DUqRLlagGAIgQF6DUqdcqcc2R+h9TKdcqcvqxvuvAerIa1AFuVdgj3rDgcg2iS0DUAd5DSrgqzWznclk8+puFsOuAS5DXoM6cgXObGdUrIrkClyPba5Yrqi1QQDaIa9BNZs/nTz878GzP35Uvqn8eemv/j6wf3KqfFMAhoG8BnV8t3Hy+Nma8w8vzHZG4fA+YUz3s+DeF5PxH/feqnWEALRDXoNSe6/P+6fXvwq9PC/y9T+vaC51knpDILJtcbBC4p8X+VF/6qk3efD2g5pHDEAn5DXI9+79xxHf7vU8LZYrQ86g1FdBJXYPe2xzo97wlZp1435Q+oRRfdDWkNcgB1+78D7ff/xsbS1965gQYV1zs51hVzazubPbfiyTzc8E4j22uYFxf5MRJt9tnHwxGQ+uHSk9dABqIa9Bsh/33n4xGf9m9TVfu7jzh1P7b5xMtHtwtntw1uJgh5xB4RVRA+N+i4Ptsrp7bHMzgbiYsYClTzXP968eP1vbe32uxnkAUAZ5DRK8POGeeDZG/SmhVC1JNne2lT6OJTNCXid2D7fSxzJ6Jk8Kpafe5Ihv9917FQaiAFAEeQ2iCF1/TzwbL0908Z68tXT+8bM1Jnogpo0PYAzIa7gDX7tgogc6HFqn2wMDIAR5Dc2spfNfTMb13IzFmD9oH8hruNnB2w9CmVhGqbr1hDF/nu9fYcwfGBjyGq46L/JfhV72T69TNwwjuHaEMX9gYMhr+Au+dvHN6uvHz9a+2zjR+lhkEsb80XizAbgT8hr+JJk5ffxszft83wAlBbqKOQAiIa+hflIoDX/9YvjrFwYb0az/zlIASZDXba0xYzCZMeabSxtj/prMmwegBfK6fbVP79x5kb/xvVQAdEFetyOhVN1uo98w5g9oh7xuL8IbUIe/fnFSILKcuf4JTxX0DoCBdoa8bhelT7U734DaJkqfapQOMIc2h7xuC8JiXSLfgNomhDF/8t41CKAJ5LXBXVmsC64Q3uWNMX9ABeS1YWFQhEjCmD9UikD/kNcGhEHHMjTWomzbnljQP+S10eABX4m91+dtONIRaIG8Ng4li3XBZRjzB/qEvDYCvS3WZQAY8wc6hLymW+MNqFgTiwSM+QNdQV5TTFhz1hhvQNUzoUsAo9dBc8hrKjXe72ywN6DqFl+7wOxQ0BzymjL0LtZlAHj7CmgLeU0T2hfrMgYZbzdM7b9xMlGLg+3sd917ONb4Z3Gww65QOJEulitEjxmMAXlNByMt1mUMwbWjO++dxXJleiHW0TtltjPsyuZW+viU+6xhvpU+DifSw65QR+/UwLg/k0WxBZpBXutdY7EuPIPrTaM2dX0YJV+tsSubXVb3fGhdZNs5sXvYY5sbdoWuZDpAA/JaZXy1FktmZgJxi4O1ONiO3qkuq9viYAfG/TOBeGr/jfhNGX6xLmM4ePvhyjSlYrkyMO53MlEZVY5wIt09OLuVPlb7MMEIkNeq2UofDzmDHb1TQ87gTCC+lT7eSh8Xy5VcgdtKHyd2D2cCcbOd6ex3jXiWc4U7Jra0z2JdxtAY87d/ctpjm1MSuMVyxeJgA5FtFQ8PjAF5rYJs7mzIGbQ42Fgyw1fvqC+fcqWl1VSX1e1kojc++WLZKkrxtQtnMPWz4W/vvBmLMeJZng+tK98OGAnyWqlAZLt7cDaWzEj9ILuy2T04m9g9bHyn8Yo4vAGVRsVypcc2p0pYC4acQRl/V2BgyGtFRr3hUW9Y9seFQie7sonFumjHV2sD43516858tWa2Mxg0Ag3Ia5mE61OVIuPofPQ//CqC6c5Umw+tTy/EVN9sJps325k7i2zQJpDXMo16wyr2CE38PsqubKq1NWixU67UZXUTSlUng78N+BPktRzsyqaTiaq7zYFx/+VaNlCEaKQSvRkAXZDXkmWy+R7bnOqbLZYr3YOzmCtBnWK50tnvIpqn6j7MAb2Q15JZHCyh6Qwkmu1AmjChnOguEruHA+N+orsAKiCvpYklM0POIKGN89Vaj20umzsjtH0gYcSzvLSaIroLvlrr6J1CSQSQ19KY7YykOeVSBSLbSgYIQut1Wd3ix1wnEom+vj6TyWSz2fJ5CQP1yD3VAUWQ1xKccqXOfhfRXeQKXJfVTXQXoK57D8fE//Di4qLwhRDc4j/YglY86B/yWoKl1dSIZ5n0Xnpsc5giQQsl91eTScLVNxOIzwTi8nYEhoG8lkDS/OCdnR3hybevr0/Sk+/0QgwvjqBFav+N2c7I+GAkEmm0tcVAoQzqyGtJJBWvfT4fx3F16U++rWnFgypkDO40mUzCXVzSpzB2COrIa0k6+13yxkdLevLF4C2KFMuVjt4pGR+MRCITExPifx6zHKGOvJZEUs9SA8dxkq5MQvNxgJD7jybljbSTdBcXlnmUsRcwEuS1BPLy2mazHR1JWHYAeU0XSf3DjZq11PY1eqGhjryWREY9xOfz7ezsSPoI6iF0kTRyIxKJPHjwwGQyeTwe8bvAKE8QIK8lkDpZRkZY19HfSBvZQ0TEw+AQECCvJZA0ni8SicgI6zrG81FIdke0SHh3IwiQ1xJIavmaPid+L6hUUodo+7cF7XegBfJaAsxHh9uQu8vi/g0NyGtp8L4nuBGhXuIWvKwVKIK8lgbvU4XbqL6EIxZvhCuQ15JhvQK4zbAr9IfoniqbOs7/8ZHdJ/5NrdAOkNeSYT0wuNHe6/O/m/rnv/nVovKJ45ls/ufDvr8ei3m+f3Ve5FU5PDAA5LUcWG8XLnv3/uOIb/epN3lSKNXrdScTHfWGZdcxYsmMxcHmChxfuwiuHX0xGUdqgwB5LZO6S6BO/B5v86ESX7vwPt9//GxtLf3ZEI5AZLvL6pb6F5LJ5i0OdsgZLJYrl3eB1AYB8lomvlobGPerEtmj89Gf/zqy9/pc+aaglX7ce/vFZPyb1dd87eL6/3vKlUa94R7bHLuy2bwMzVdr4UR6xLPcY5u7rWsEqQ115LVCo96wkuF3xXJlYNzPrmyeF/mn3iQTPVDx2ICclyfcE8/GqD91Z3RmsnknE+2yursHZ6cXYjOB+NJqait9nNg9FF48MjDuv/9octgVErPcF1K7zSGvlQpEtrsHZ8XPU29gVza7B2cv16yZ6MFTbxLXoZ6dF/nJ4E9PPBsvT6SN3MjmzuZD6zOB+Ihn2eJgB8b9Ql7L6LS4nNqlTxjt10aQ1yrI5s6GnEGLg40lM3f2Mp1ypaXVVJfV7WSi10eD7L0+759eR21Eh/jaxTerrx8/W3v+guCEKfEaqc1ED5DabQJ5rZqt9PGQM9jROzXkDM4E4lvp4630cbFcyRW4xvOv2c509rtGPMtNCppCbeSb1dctPHa4w1o6//jZmvf5vt6SsfSpxkQPkNptAnmtMr5aiyUzM4G4xcFaHGxH71SX1d14/hU/l937fH/46xe4AjV3UigNf/1ixLf77v1HrY/lVkjtNoG81q9k5vTxszWpdVJQS+lTzfP9q8fP1pKZU62PRRSktuEhr3XtvMg/8WygNtJ6322cfDEZD65JWMhNJ5DaBoa8pgBqI60kdPl+FXpJ9S8cqW1IyGs6oDbSAo1p5QdvP2h9LOpAahsM8poaqI2Qw9cumOjB9WnlxoDUNgzkNWVQG1GdMK2ciR7cOK3cMJDaBoC8pk8yc9o/vY7aiHIHbz+InFZuGEhtqiGvqfTu/cen3iSNoxd04rzIfxV62ba3PaQ2pZDXtOJrF57vX434dnG9SdKYVv7dxonWx6Kxy6lt7FqQYSCv6baWzrdtI1EGoZSkw2nlGmqkdnDtCKmtc8hr6qE2IoYwrXz46xfCEjBwxXmR93z/Cqmtc8hrI0BtpAnqppVrCKmtc8hr40Bt5LrvNk4eP1vDw4ckSG3dQl4bCmojDY1p5e0zVk9dSG0dQl4bjVAbGfWn2rY2srZ39CvWUNPKNdRI7f+98jKbO9P6cNod8tqYftx7+8Sz0Q6BJbxwXFjZ9t7DsXsPx/7q74P/7pfeew/HOvtdwprIzZe7hRtlsvnphZjFwd5/NPmv/tNv/v1/C/zs6e/vPRy7/2jS4mCnF2KZrAHn7usc8tqwTgqlJ54NA48yFhYgFxb0CUS2r8fHKVdK7B6OesNdVrfZzty29Dhcwa5sdva7emxz86H1rfTxlSXu+GptK308H1rvsc119rvYlU2tjrMNIa+NjK9dfBV6abzaCF+tzQTiXVZ3ILJ954KZgtT+G2HFH7QKm4glM7etLHqjU64krP4uY71pkAF5bUyp/TdOJiok1L/58n/924F/aixLxq5sUl0fOOVKZjszE4iLTOrLttLHZjsTTqRJHBjtnEx0yBmU8beRK3BDzqCTiZI4KrgMeW0oQomgs99ltjPsyqaw5q+Qa41lf4UGUffgLLuyKSPytJXJ5ntsc0rayHy1NuwKTS/EVDwq2hXLFeFGrmQj7MrmwLi/WK6odVRwHfLaIIrlSqNEIOZhNps7czLR7sFZihqbqf03Zjsj8lG9uZlAfNQbVr4dA+CrNbOdSeweKt9UYvfQbGeoawRQBHltBEKrU0aJIFfghl2hIWdQ/9dYrsCpFdYCJxNFX1m9Xh9yBlWsPseSmSFnUK2twRXIa+rFkhmLg1VSko4lM2Y7o+eittAGVL2rcGDcr0q7kl7TC7H50Lq625wPraPcRAjymm5Lq6khZ1B50TCTzSsMfaIItYVPuVKX1a3/ZwtChMcyEltW2McAt0FeU2wrfTww7lcrbrK5M7Od0WF/EdFUbefGoNnOpPbfkNiy0NNAYsttDnlNq1yB67HNqRuvid3DgXG/ihtUxbArRK5TlK/WuqxuFcvitCBdaFa3LA4C5DWtCD1ykihoKlEsVzr7XURLFjOB+EwgTm77+mRxsEQnfG6ljy0Oltz22xPymkrkGkd6a2+GE+lhV4joLtrw4b0Fd0G+Wuvsd+mwvEY15DV9SEcqu7Kpn7lqI57lpdUU6b109rv0c4tqgRbcBeuEC1ntCXlNn6XV1Ihnmdz2ddUykpSkps+J30u7JcuoNxyIbIv/+aOjo76+PpPJ5PP5xH8qENnGpCR1Ia/p04JwaU2rVox7D8fE/7CkjL6s3ebOSOoM5Diur6/v6OioXq8nEgnxe8HcGdUhrynTmsZva56X75QrcF1Wt/ifl53XuioBtYCkzmqfz/fq1SsZeyE3vrttIa8pI6NzbHFxUWqQFcuVjt4pSR8hQerJNiohkh7b6+RLTHrTZXWLnxvV19e3s7Pz4MEDk8k0MTEhfi9Sb7dwJ+Q1ZaQmSz6fn5iYkNHw7Oid0ryEnc2ddQ/OSv0Ux3E+n8/j8Yj/CPK6CZPJtLi4KHwt6ReLvFYd8poyUufjTUxMHB0dycjr7sFZzdfrU9LMl3TK7TYEW9Lg6yu/SfG/WAzBVh3ymjKSevZ3dnaEyoCMvCY9n0Kk+48m5Q0TlnTK+ulfbQ1J59vX18dxf2mMP3jwQOQH2+2ppQWQ15SRNJKhr69P+ILevJb0jovLj+2SStg6OdmWkfQ8EYlEGjUQn8/X+CWruxcQA3lNGfH1kMXFxcboKxl5LanESY6ka17oWX3w4IGksNZJ52orSR25IfxipXbk4i19qkNeU0b8SDvTNZJ2JLsQoa4WjAlrz8d20vdjdDaSgLymjLyXXUgN61Ou1NnvkroXQkgnS3u+SY70FKF2G9LeGshr+sgYaSc1r3XV5CQ6eadt53QQfau43t4aZhjIa/q0YDCD3pqc5Cqh5N7Zr3/k1mrQ21t5DQN5TR/Sr2Xgq7WO3ik9FK8bCI3k1cm0e63w1Vr34KzqtaZcgesenNXV349hIK+pRLTnXZ+VR9WPKpPNm+1Mm8eK6ovAFcsVs53RfKaVUSGvqUSuia3nJWhHveH575KqbOrgX87+1v5PehiwqLnE7uGXY9+q8l+cr9a+HPu2zZecJwp5TStCJWapb0Zupf+3/S9/7fi/yqdgZLL5HvvCf/6HNb52ocqBUe3d+4//8X/+8MvxPyhsZRfLlV+O/+HvnLGXJ7gLkoK8plWxXOmxzanbQtRzPbf0qfb42dp5kZ8JxIddIdnhEk6kzXYmV+CY6AETPVD3IGk0/PWLZOZ0K32spMgmDLPZSh+/e/+xf3q99EmPz2cGgLymWDZ39rf2fzz740dVtpbaf2NxsPqshNTrdc/3r4JrR8LX4US6y+pmVzYlHa3QaTnsCjU+9cSz0eaNwbV0fsS3K3ydK3A9trkRz7KkcXinXGnEs3y56bD3+vypV52yFVyBvKab1Z3osX+jfKBrYvfQ4mA1f4HqbQ7efuif/mx8WLFccTLR7sHZmUC8eavwlCstraYGxv3XXxLy7v3Hx8/atyrC1y6+mIyfF/nL31xaTXVZ3aPe8J3VtlgyM+oNd1nd10eXfrP62vt8X+XDBeQ11YJrR57vXwmPokqGi7ArmwPjft2Gdb1e759eP3j74fr3cwVuJhDvsc119ruGnEHhZSOJ3UN2ZXMmEB/1hs12prPfNeJZvq0T7PmLN5PBnwgfvk5dfmS5jK/WApHtIWfw/qNJi4OdXojNBOLhRDqcSM8E4tMLMYuDvf9ocsgZDES2b3vEGfHtrqXx8hCVIa9ptff6fPjrF0Lb8JQryXiSrf95drsOR+9dJtyWmv/MKVeKJTNCXg+M+51MdCYQD0S2xcyFac9kuf7Ich1frW2lj+dD60KfwbArNBOIz4fWt9LHd1aiSp9qTzwbJwVMcVQT8ppK50W+f3r9tidZMW1tYUSg/mf3nRf5x8/WiPZf3fjLNLwW1O5PCqX+6fW2LTeRgLym0lNvcu/1+fXvC0+yQn1g1BueCcS30seNf0ILVHjO1duM89uM+lM/7r0lvZdk5nT46xek96If322cfBV62YId/bj3dtTfRgtBkIa8po+YgWinXCkQ2Z4JxC0OtvFPqPDGkhndDgK5opUjDb4Kvfxu46Q1+9JWi58nbquSgwzIa8q0T0uQr130T6+3rADa4t1paDL40/MXrSuC8bWL4a9f3Pg4CFIhr2nSVpMRWj8m7OUJ99SbNHa99eUJ98Sz0eKdtmcPAQnIa2rwtYun3mSbzO/QamS0sSc98rWLJ56NG0dGktYO98IWQF5To63qgMIkaU12beBJj9pOYxEzLhOaQ17T4fK8YcPT9mSNOunxvMh/MRnX9rxaXDo3HuQ1BdpqHOuNk6RbzJCTHvUwLUjDgowxIK/1rn3GLQh0UvbRQ7qpSD/PZ23VZ6465LXetdUj5MHbD088G3p4kjDSkAa+dvH42dq79+q8x1G59hmTqjrkta4Z8sG8CV319RkmVrzP979Zfa31UXzG2ONwyEFe65d+GputocObkwEmPeq288NgFafWQF7rVOlTrX96XT/PsKTps/5ggM6D2141o7l2+wtXBfJap9qt9aHbMj3VEz10+MhymW7b/rqFvNajdptZoMkkafEoLbY2VrzU+kCa0fkdRW+Q17pDdYNOBirG5OqqI1QkWorvOhnBSQXktb7os4xLFBUPE9RNehSzfIxOtNWLcRRCXuuLbnuHCNHDJGmR6Hpyv23FS31qw2aKPMhrHaG0TqoEXd2qtBwtFY8sV1xejxRug7zWi1aupaIT1E1IoaIZ2IIVLwmh8TbTYshrXWjDlyrobZK0SPq/x7RmxUtCqD74FkBea689+1t0OElaJD2Pu9D/7aQ5A0xQIgp5rb02HM9E9UQJ3WaKbg9MkjZ81hQPea0x/bzospVoHwajzzHyhumvbs+LQgzktZZOCqUnno12a0r8uPd21J/S+iiU0ls4UjdCvDm9/Xp1AnmtGWM8vUpFxSRpkXQ16VHDFS8JMd4ZKYe81oxu33BElJGK9fpp0hqygIAX+F2HvNYGXZPl1ELRJGmR9PDfUQ8rXhKiz34CDSGvNdBuCxE00DVJWiTNJz0a6ZHlOj3cEfUDed0iuQK3lT5eWk1N++M//3Vkil3dSh9vpY+1Pi7ihNOcCcSH3D/+8rc/LK2mttLHuYJeyr5KpPbfbKWPf/tN/Oe/jvz2m3grTy2bO9tKH7MrmxP/uPrzX0fmQ+tb6ePUvqHKa41L5stnP/xXz48zgXibXDJNIK/JyubOphdiPba5Lqvb4mBHPMu/+zb+G9/qTCBucbAWB9vROzXsCi2tpviqcUaJ8NVaOJEedoU6eqeE05wJxH/jW/3dt/ERz7LFwXZZ3d2Ds9MLsUyWgtdxXCac2ohnuaN3ymxnWnxqW+ljJxMVdmFxsE4mOu2PT7Gr0wsxi4M125nOfteIZzmWzKi+65a585K5/2jSeJeMSMhrUnIFbsgZ7B6cnQ+tN7l0i+WKcP13Wd2ByHYrj5CQpdVUl9U97AqFE+liuXLbj2VzZ/Oh9R7b3MC4P5s7a+URyhZOpIVTW1pNtfjUUvtvhNsDu7LZpAl/ypWWVlPCHx51qS3ykmncMg1zyYiHvCZieiEm9YI55Uqj3nCPbY66JmdDJpvvsc2NeJZPOQmDFBO7h92Ds04mqufmUjZ31mObG3aFWn9qxXJl2BUy2xlJ5Y5s7mzIGbQ4WFpKT7IvmS6r22CFoCaQ1yorlisD4/750Lq8SzSTzZvtDHUto3q9HktmzHZG9s2GXdm0ONgmjVYNJXYPtTq1XIEz25lwIi1v11vp4x7bnM7jTOElkytwFge7tEr9DCwxkNdqEq6uxO6hko3w1dqQMzgfomnc23xofcgZVNhATu2/6bHN6a09yK5sDoz7Fd5I5J2akLYKKyrFckXPcabWJTPiWZ4JxNU6Kt1CXqumWK4ov7oaRr1hdmVTlU2Rxq5sjnrDqmxKuHol1RyIEnpNVdmU1FPL5s7MdkaVBw6hBaDDhzZ1L5nphRhdrRwZkNfq4Ku1gXG/uoONBsb9CtsdLZDYPRwY96u4wdT+G4uD1UMtW/UjEb9BIchUfNTgqzUlJR0SSFwy+rwtqQh5rY5Rb1j1rmrVL1rVqdgGvGxpNTXiWVZ3m1KdcqUe25zqLX2Rp2ZxsKoPNM4VuB7bnH56CEhcMny1pmKDXYeQ1yoQxkWQ2HIsmRlyBklsWRXkmjNSh0OojkSaCO48NRWLMFewK5tOJkpiy1KRu2RUf+DTFeS1Cog+hel2hB+5S470xrXde/ON89Val9VNqIJPdOOSEL1kDFwVQV4rRfp+LkyUILd92Ug3gTW86kjvusn2STeByTXexSN9yWh7sycKea0UuQfnhs5+lx7aRJedcqXOfhfRXWiVLMVypbPfRbTDs8mpkb4LtuDs7tSCS6Z7cNaQVWzktVJdVjfpLsERz7Lexs+2oEtQq2RpwX3itlNrwV2wTqYzU5IWXDJGHduHvFakNcUKHfY6tmasoSbJ0pq7442n1pqBMdr2OrbmktlKH1scLOm9tB7yWhFJF5jpkgcPHojfS67AdVndsg6QFElNpHw+b7PZTCZTX19fPi+h79TJRFs/aUhqB+/ExITJZJqYmJC0lxtPTcz55vP5xcXFvr6+K9+PRCIPHjwwmUyLi4vNt6Btlom5ZG47x9u+f12xXOnonZJ/lHqFvFZkJhCXMQs2n8/7fD5JH7n3cEzqXoiSdDx9fX07Ozv1ev3Vq1eSblTzofXphZjkg1Omo3dK/CBln88n5KPP55P03/TGUxPTzzkxMXF0dGQyfXbl7uzs2Gw24WubzRaJRJpsQdvbv5hL5sZzbPL9G91/NKmHWVfqQl4rIq/nZHFx8dWrV5I+oqsuR6ll1ssXmKS8bn2XI1+t3X80Kf7nL5+amHZfw42nJr6z8UpmTUxMNP6ijo6OGtl9I6nnqC7xl8xtuSwyrw3Z5Yi8VkR4y7PUTzW/nG7Ugi4a8bK5s+7BWfE/v7i4KLQ9fT5f86bfFa1/cpfa9rycHSJzRHDjqYn/r3xlX83/53UaPj4cTgwAAA1nSURBVK6Jv2QU5rXm3aokIK8VkVFgffXq1Z0VxuskPaSTJqM42NfXZzKZPB6PpE9pMjFdUpZ5PB7hDhSJRCTl9Y2nJj5ilOS1trVd8ZeMwrzWVRNHLchrRWQUWD0ej6Q+t7rWD7A3klQcFGq7HMd5PB5J9yp53QMKSSo95fN54VYkdPeJ38uNpya77Skpr6U+HqlL/CWjMK/11uWjCuS1IjIagJKqnAJtL7AbSWq8yC4atGBixXXyZqwIdyPxP3/jqYkfNXzl12iz2Y6O/rRE+tHRUfPBKtq+YUP8JaMkr1szkr31kNeKSC13JhIJGcUQPbyv7gpJg5Qb40N2dnYk3a40eXeK1BqXcGoej0f4QqQbT038QPsrmRWJRC6PD2l+JJo8tTSIv2SU5LUOpyyoAnmtlKRMsdlsUoshdV2+v0bS9dAoGkg6fa2GnUnt5PT5fGJGPV9226nx1VpH71TzQpPpc43vLy4uCuP67+zR1fwNYncewG3neNv3r9PhlGBVIK+VIt1aEXMNt14LjioQ2VZr2RpJ+Gqts99FtHe3yamRnjiqh7lXLWjg62r8q4qQ10oJK+SSSy49vFDtRvLGMoqnYTOQ9LzKJqdG+kFekylIV5C+ZIxaDKkjr1VB7vLWzwuLrzvlSl1WN6GrTttLTttTI3ejInpekhC9I2pe8CEHea0CcpeBfhYEuRGhq04PdylCv3kxp0bu9c2avI/lRm17ySiEvFYHiWJrNnfWY5vTQ2voNsVyxWxnVJ/1q4dY4as1i4NV/VXUIk+NxG9Ab6+sI3HJ6G2NStUhr1Wj7jWm/8V2BapfIVp1M153ypXMdkbF/wSSTk3djkd9BpnqlwyJ1oOuIK/V9De/WvxDdE/5dorlCkVvPxAabqpkgVDb1c8jhdAzpkplRuqpCemjSgM/V+B0G2SPHP9n/nsJ49ZvUyxXhpzBFryTXVvIa9U8f/Fm4tvUsCuksP9dKIPQEtaCrfRxj21OYSKwK5u6CmuB8H59hf1X8k7tlCtZHKzCQTip/Td67n/70pX4L1NLCi+ZXIGzOFjDh3Udea2W5y/eTAZ/Er6eD60PjPvlhRe7sqnuM3jLCI04eY+3uQI35AzqtpuocWoy7iUKT42v1oZdoVFvWEYbn6/WZgJxtR59SDgv8r8Yi9WVXTJLqyk935DUhbxWQTJzOuLb5WsXje8kdg+7B2edTFT8ZRZLZoSP6PbqulOxXHEy0S6rW/xszGK5Mr0Q6x6c1dsEziv4as3JRCUdp4qnFohsdw/OzofWxd8wApHtLqt7JhDX2/PKZZdbObIvmRHPMr2XjFTIa6Wuh3UDu7LZ2e8aGPezK5u3NZljycyoN9xldQ85g/qsMEoltCg7+12j3vBtUZUrcIHI9sC4v6N3SlIMaatxaiOe5Vgyc+NhEzo1If07eqeGnMGl1dSNocZXa+FEesSz3NE7Ja9J3mIjvt219GftYjGXTGL30GCXjHjIa0VennBPvckbw7ohsXsotDrvPRzrsrotDlb4d+/h2L2HY0POYCCyTWMBpLlTrhSIbA85g8JpNs668XsY9YYpLTiecqWl1dSQM3j/0WSLT42v1mLJzIhnubPfde/hWI9tTti12c7cezh2/9HksCu0tJqior3J1y5+MRYrfbrhftb8khkY9xvykhEDeS3fwdsPT73JG//gbpMrcFvpY+EfuQPTocZZG+8y0/DUMtm8sGvVx4m3wN7r86fe5J0/1raXzI2Q1zKdFEpPPBuSwhoAGjzfvwquHWl9FJRBXsvx7v3Hp97ku/cftT4QAFp9MRnHFSQV8loyhDWAQu/ef/xiUrM1E+iFvJam9Kn21Js8ePtB6wMBoFhw7cjz/Sutj4I+yGsJENYAqnjqTe69Ptf6KOiDvBaLr1089SZfnhhteANAi/G1i585fmg+ChZuhLwWha9djPh2k5lTrQ8EgHpr6fyIb1fro6AS8lqU4a9fIKwBVDEZ/On5C/oGjOsB8vpu+PMCUNEvxmLnRV7ro6AS8voOCGsAFR28/dA/va71UdAKed0MEz1gogdaHwWAceCaUgJ5fSv8YQGo7olnA4OsZENe3wzj+QFUV/pU+5njB62PgmLI6xtcfo06AKgFV5ZCyOurftx7O+pPaX0UAAY06k/9uPdW66OgGPL6M00WiwEAJZosUAAiIa//AmENQI7IBQqgCeT1nxy8/fDEs4GwBiDE+3z/m9XXWh8F3ZDX9bqslb0AQJLHz9ZOCnpfAljnkNf1d+8/9k+vI6wByMECBapo97zGYjEALfDdxslXoZdaHwX12jqvz4v8E88GwhqANLzhUhXtm9dYLAagNbBAgVraMa8z2fw/72a/dP3zDy+yWh8LgPFhgQK1tEVeF8uVcCI97Ap19E7dezjWY5t79D++Nf/K32Obu/dwrKN3asSzHE6ki+WK1kcKYEBfhV5+t3Gi9VEYgcHz+pQrOZloZ79r2BW6LZGL5crSamrYFersdzmZKFIbQF1fTMbRS6QKI+f1TCDePTjLrmzyVVFj9fhqjV3Z7LK62ZVN0scG0CawQIGKjJnXxXLF4mBnAnEZjeViueJkokPOoMiUB4DLcgWOXdkcGPd3D87eezj2rx//7n6f597Dse7BWYuDZVc2s7kzrY+RVgbM62zuzGxnttLHSjYSS2bMdiZXwIvVAcQKJ9Ldg7NdVreTiSZ2D6/kcjZ3tpU+djJR4WcCkW2tjpNeRsvrXIEz2xlVbuCZbN5sZ045zKAFuMNW+rjHNjfsCom89HIFbtQb7h6cTewekj42IzFUXvPVmtnOZLJ5tTaY2n9jcbAojAA0MROIWxysjOsumzsbGPc7mSiJozIkQ+X1kDMYS2bU3ebSamrEs6zuNgGMga/Whl2hmYCiF4MIxW6MyxLDOHkdS2aGnEESWyZxGwCgHV+tWRxsOJFWvqnE7qHZzuBB9k4GyWu+WuuyugnVmjPZfI9tjsSWAeglzGlQa2vk2ltGYpC8Zlc2iVbBRr1hdGcDNMyH1qcXYvrfpsEYJK+7B2eJDurcSh9bHCy57QNQhNwTp9nOpPbfkNiyMRghr3MFrsvqJr2Xjt4pdIkA1Ov1gXE/oXF4qD02Z4S8Jl0MEYx4lpdWU6T3AqBzpAvN6N5vwgh5fWe/Rz6fX1xc7Ovru/L9nZ2dvr4+k8nU19eXz98xejQQ2R71hpUeKwDlyDWuBan9N2Y7Q277VDNCXt9Z85qYmDg6OjKZrp6sz+fjOK5erycSietpfkVi93Bg3K/wUAGoxldrHb1TpAfedfa7MK/4RkbI6y6rW8yLPq7ntfj/t47KGkCrRt2h9ngbI+T1vYdjYn6sSSJzHDcxMdH8463p1QTQMzEDW28sPwqPsCaTyWaz3Vl7xKTi2xghr0U+PTXJa5vNdnR01Pzj2dxZ9+Cs5IMDMBAxnYE3lh8XFxeFL8TUHjF89jZGyOse25yYd83cltc+n29nZ+fOj+NvCED8+OgmzaM7a494lr2NEfJa5ACgG/9KRIZ1Hc9oAKL7iuq3h3IkEmm0tW/DV2v3H01KPrg2YIS8nl6IzYfuXnDo+h9QJBIRGdbi9wJgYEry2mQyCWNn7/xssVzp6J2Sc3xGZ4S8vnPApulzd37/RqSnvAPon8XBily5qUn7+s6+fYzFuo0R8rpOfsAmOhsB6lLeyaekfo25DrcxSF47mSjRRc3x5jCAer0+E4iLXJ3gtvEhYtrXrXnDBI0MktenXKnL6iY07eqUK3UPzuJlTwBiJovfWGaMRCIPHjwwmUwej+fOvYivurQbg+R1nWR/IOnGOwBFSNcei+VKZ78La83cyDh5zVdr3YOzIjuvxcvmznpsc/jrARCQXrsjnEgPu0Lktk814+R1vV7P5s7MdkbFwkWxXOmxzal+DwCgF9HaI1+tme2MjKXW24Sh8rr+555lVf6Y+GptYNyPOhrAFeQqhOhpbM5oeV2v15dWUwPjfoWt7FOuZLYzRN/zC0ApQrXHYrnSPTiLN6k2YcC8rtfrW+ljkS8VIfFxAMPLZPNmO6NiVQSPs2IYM6/r9XquwPXY5oacQUmtgFyBG3IGLQ4WN3mA5tR9FzbpbkxjMGxeC2LJTJfVLUzKalIhKZYrQq90l9WNteMARJoPrQ85gwprj3y1NuwKiZyG0+YMntcCIYs7eqcsDlb4y2j8G3aFzHamo3dK/ERbAGiIJTMWByv71TqnXMniYHHpidQWed2wlT4OJ9KX8zqcSIt8ny8A3CiTzXcPzjqZqKQqYrFcmV6IdVnduADFa6+8BgBC2JVNIbXvzN9MNj+9EOsenJ0PrWMmmiTIawBQR7FcYVc2zXams9814lmeCcTnQ+tb6eOt9DG7sjkTiI94ljv7XT22ufnQOrr0ZUBeA4DKTrnS0mpqJhCfXohZHKzFwTqZ6EwgvrSaQkwrgbwGAKAD8hoAgA7IawAAOiCvAQDogLwGAKAD8hoAgA7IawAAOiCvAQDogLwGAKAD8hoAgA7IawAAOiCvAQDogLwGAKAD8hoAgA7IawAAOiCvAQDogLwGAKAD8hoAgA7IawAAOiCvAQDogLwGAKDD/wek8NWmu+4KSAAAAABJRU5ErkJggg==" alt="" />

条件:

1、顶点的标号从1到V,根节点是1

2、给定顶点A和B, 求最近的祖先

代码1:

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std; #define _DEBUG 0
#define MAX 10001 int T;
int Answer, nCount;
int N, E, src, des;
int tree[MAX][MAX];
int count[MAX];
int parent[MAX];
bool visited[MAX]; void InitData()
{
for(int i = ; i < MAX; i++) {
for(int j = ; j < MAX; j++) {
tree[i][j] = ;
}
visited[i] = false;
count[i] = ;
parent[i] = ;
}
} int _Count(int node)
{
int cnt = ; for(int i = ; i < count[node]; i++) {
cnt += _Count(tree[node][i]);
} return cnt;
} int main()
{
// freopen("input_commonancestor.txt", "r", stdin); cin >> T;
for(int tc = ; tc < T; tc++) { Answer = ;
nCount = ; InitData(); cin >> N >> E >> src >> des; int start, end;
for(int i = ; i <= E; i++) {
cin >> start >> end;
tree[start][count[start]++] = end;
parent[end] = start;
} int node = src;
do { //找出src的所有父节点,并置为true
visited[node] = true;
node = parent[node];
}while(node); node = des;
do { //从des点出发找父节点,每个父节点判断是否为true
if(visited[node] == true) break;
node = parent[node];
}while(node); if(node > )
nCount = _Count(node); //找出以node为顶点的树的结点个数 cout << "case# " << tc << " : " << node << " " << nCount << endl;
}
}

代码2:

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std; #define _DEBUG 0
#define MAX 10001 int T;
int Answer, Count;
int N, E, src, des;
int graph[MAX][MAX];
int hash[MAX];
int visited[MAX]; void InitData()
{
for(int i = ; i < MAX; i++) {
for(int j = ; j < MAX; j++) {
graph[i][j] = ;
}
hash[i] = ;
visited[i] = ;
}
} void FindParent(int v)
{
hash[v] = ; if(v == )
return; for(int i = ; i <= N; i++) {
if(hash[i] == && graph[i][v] == )
{
hash[i] = ;
FindParent(i);
}
}
} void FindAncestor(int d)
{
if(hash[d] == ) {
Answer = d;
return;
} if(d == ) {
return;
} for(int i = ; i <= N; i++) {
if(graph[i][d] == ) {
FindAncestor(i);
}
}
} int _Count() //BFS计算顶点个数
{
int res = ;
queue<int> q; visited[Answer] = ; q.push(Answer); while(!q.empty()) {
int top = q.front();
q.pop(); res++; for(int i = ; i <= N; i++) {
if(visited[i] == && graph[top][i] == ) {
visited[i] = ;
q.push(i);
}
}
}
return res;
} int main()
{
freopen("input_commonancestor.txt", "r", stdin); cin >> T;
for(int tc = ; tc < T; tc++) { Answer = ;
Count = ; InitData(); cin >> N >> E >> src >> des; int a, b;
for(int i = ; i <= E; i++) {
cin >> a >> b;
graph[a][b] = ;
} FindParent(src); #if _DEBUG
for(int i = ; i <= N; i++) {
for(int j = ; j <= N; j++) {
cout << graph[i][j] << " ";
}
cout << endl;
}
for(int i = ; i <= N; i++) {
cout << "hash[" << i << "] = " << hash[i] << endl;
}
#endif FindAncestor(des); if(Answer == )
Count = N;
else
Count = _Count(); cout << "case# " << tc << " : " << Answer << " " << Count << endl;
}
}

输入文件:


上一篇:Linux下swap分区多大才合适的问题探讨


下一篇:JAVA的SSH框架登录注册