{"id":25267,"date":"2025-04-19T12:06:19","date_gmt":"2025-04-19T04:06:19","guid":{"rendered":"https:\/\/www.wsisp.com\/helps\/25267.html"},"modified":"2025-04-19T12:06:19","modified_gmt":"2025-04-19T04:06:19","slug":"%e3%80%90%e6%a0%91%e4%b8%8a%e5%80%8d%e5%a2%9e%e3%80%91%e3%80%90%e5%89%b2%e7%82%b9%e3%80%91-%e3%80%90%e6%8d%a2%e6%a0%b9%e6%b3%95%e3%80%913067-%e5%9c%a8%e5%b8%a6%e6%9d%83%e6%a0%91%e7%bd%91%e7%bb%9c","status":"publish","type":"post","link":"https:\/\/www.wsisp.com\/helps\/25267.html","title":{"rendered":"\u3010\u6811\u4e0a\u500d\u589e\u3011\u3010\u5272\u70b9\u3011 \u3010\u6362\u6839\u6cd5\u30113067. \u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee"},"content":{"rendered":"

\u4f5c\u8005\u63a8\u8350<\/h2>\n

\u89c6\u9891\u7b97\u6cd5\u4e13\u9898<\/p>\n

\u672c\u6587\u6d89\u53ca\u77e5\u8bc6\u70b9<\/h2>\n

\u6811\u4e0a\u500d\u589e \u6811 \u56fe\u8bba \u5e76\u96c6\u67e5\u627e \u6362\u6839\u6cd5 \u6df1\u5ea6\u4f18\u5148 \u5272\u70b9\u539f\u7406\u53ca\u5c01\u88c5\u597d\u7684\u5272\u70b9\u7c7b(\u9884\u8ba12024\u5e743\u670811\u53f7\u5de6\u53f3\u53d1\u5e03）<\/p>\n

LeetCode3067. \u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee<\/h2>\n

\u7ed9\u4f60\u4e00\u68f5\u65e0\u6839\u5e26\u6743\u6811，\u6811\u4e2d\u603b\u5171\u6709 n \u4e2a\u8282\u70b9，\u5206\u522b\u8868\u793a n \u4e2a\u670d\u52a1\u5668，\u670d\u52a1\u5668\u4ece 0 \u5230 n – 1 \u7f16\u53f7\u3002\u540c\u65f6\u7ed9\u4f60\u4e00\u4e2a\u6570\u7ec4 edges ，\u5176\u4e2d edges[i] = [ai, bi, weighti] \u8868\u793a\u8282\u70b9 ai \u548c bi \u4e4b\u95f4\u6709\u4e00\u6761\u53cc\u5411\u8fb9，\u8fb9\u7684\u6743\u503c\u4e3a weighti \u3002\u518d\u7ed9\u4f60\u4e00\u4e2a\u6574\u6570 signalSpeed \u3002 \u5982\u679c\u4e24\u4e2a\u670d\u52a1\u5668 a ，b \u548c c \u6ee1\u8db3\u4ee5\u4e0b\u6761\u4ef6，\u90a3\u4e48\u6211\u4eec\u79f0\u670d\u52a1\u5668 a \u548c b \u662f\u901a\u8fc7\u670d\u52a1\u5668 c \u53ef\u8fde\u63a5\u7684 ： a < b ，a != c \u4e14 b != c \u3002 \u4ece c \u5230 a \u7684\u8ddd\u79bb\u662f\u53ef\u4ee5\u88ab signalSpeed \u6574\u9664\u7684\u3002 \u4ece c \u5230 b \u7684\u8ddd\u79bb\u662f\u53ef\u4ee5\u88ab signalSpeed \u6574\u9664\u7684\u3002 \u4ece c \u5230 b \u7684\u8def\u5f84\u4e0e\u4ece c \u5230 a \u7684\u8def\u5f84\u6ca1\u6709\u4efb\u4f55\u516c\u5171\u8fb9\u3002 \u8bf7\u4f60\u8fd4\u56de\u4e00\u4e2a\u957f\u5ea6\u4e3a n \u7684\u6574\u6570\u6570\u7ec4 count ，\u5176\u4e2d count[i] \u8868\u793a\u901a\u8fc7\u670d\u52a1\u5668 i \u53ef\u8fde\u63a5 \u7684\u670d\u52a1\u5668\u5bf9\u7684 \u6570\u76ee \u3002<\/p>\n

\u793a\u4f8b 1： \"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n

\u8f93\u5165：edges = [[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]], signalSpeed = 1 \u8f93\u51fa：[0,4,6,6,4,0] \u89e3\u91ca：\u7531\u4e8e signalSpeed \u7b49\u4e8e 1 ，count[c] \u7b49\u4e8e\u6240\u6709\u4ece c \u5f00\u59cb\u4e14\u6ca1\u6709\u516c\u5171\u8fb9\u7684\u8def\u5f84\u5bf9\u6570\u76ee\u3002 \u5728\u8f93\u5165\u56fe\u4e2d，count[c] \u7b49\u4e8e\u670d\u52a1\u5668 c \u5de6\u8fb9\u670d\u52a1\u5668\u6570\u76ee\u4e58\u4ee5\u53f3\u8fb9\u670d\u52a1\u5668\u6570\u76ee\u3002 \u793a\u4f8b 2： \"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n

\u8f93\u5165：edges = [[0,6,3],[6,5,3],[0,3,1],[3,2,7],[3,1,6],[3,4,2]], signalSpeed = 3 \u8f93\u51fa：[2,0,0,0,0,0,2] \u89e3\u91ca：\u901a\u8fc7\u670d\u52a1\u5668 0 ，\u6709 2 \u4e2a\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9(4, 5) \u548c (4, 6) \u3002 \u901a\u8fc7\u670d\u52a1\u5668 6 ，\u6709 2 \u4e2a\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9 (4, 5) \u548c (0, 5) \u3002 \u6240\u6709\u670d\u52a1\u5668\u5bf9\u90fd\u5fc5\u987b\u901a\u8fc7\u670d\u52a1\u5668 0 \u6216 6 \u624d\u53ef\u8fde\u63a5，\u6240\u4ee5\u5176\u4ed6\u670d\u52a1\u5668\u5bf9\u5e94\u7684\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee\u90fd\u4e3a 0 \u3002<\/p>\n

\u63d0\u793a：<\/p>\n

2 <= n <= 1000 edges.length == n – 1 edges[i].length == 3 0 <= ai, bi < n edges[i] = [ai, bi, weighti] 1 <= weighti <= 106<\/sup> 1 <= signalSpeed <= 106<\/sup> \u8f93\u5165\u4fdd\u8bc1 edges \u6784\u6210\u4e00\u68f5\u5408\u6cd5\u7684\u6811\u3002<\/p>\n

\u6811\u4e0a\u500d\u589e<\/h2>\n

\u672c\u9898\u6709\u4e09\u4e2a\u8003\u70b9： \u4e00，\u5982\u4f55\u8ba1\u7b97\u6811\u4e0a\u4e24\u4e2a\u8282\u70b9x1,x2\u7684\u8ddd\u79bb\u3002 \u5047\u5b9a\u8fd9\u4e24\u4e2a\u8282\u70b9\u7684\u6700\u65e9\u516c\u5171\u7956\u5148\u662fpub\u3002\u4ee5\u4efb\u610f\u8282\u70b9root\u4e3a\u6839，f(x)\u8868\u793a\u8282\u70b9x\u5230root\u7684\u8ddd\u79bb\u3002 x1\u5230x2\u7684\u8ddd\u79bb：f(x1)+f(x2)-2*f(pub)\u3002 \u4e8c，\u5982\u4f55\u627e\u5230\u6700\u65e9\u516c\u5171\u7956\u5148：\u6811\u4e0a\u500d\u589e\u3002 \u8bb0\u5f55\u5404\u8282\u70b9\u76841\u7ea7\u7956\u5148（\u7236\u8282\u70b9）\u30012\u7ea7\u7956\u5148\u30014\u7ea7\u7956\u5148\u2026 \u4e09，\u5982\u679c\u5224\u65adac\u548cbc\u6709\u516c\u5171\u8fb9\u3002 \u6811\u662f\u8fde\u901a\u65e0\u5411\u65e0\u73af\u56fe，\u56e0\u4e3a\u65e0\u73af，\u6240\u4ee5\u4e24\u4e2a\u8282\u70b9\u7684\u8def\u5f84\u552f\u4e00\u3002 \u5047\u8bbe\u516c\u5171\u8fb9\u662fx3x4\u3002\u5219x3\u5230c\u7684\u8def\u5f84\u552f\u4e00，\u5047\u5b9ax3\u5230c\u7684\u5012\u6570\u7b2c\u4e8c\u4e2a\u7aef\u70b9\u662fx5，\u5219ab\u548cbc\u7684\u6700\u540e\u4e00\u6761\u8fb9\u90fd\u662f <\/p>\n

x <\/p>\n

3 <\/p>\n

c <\/p>\n

\u2192 <\/p>\n

\\\\overrightarrow{x3c} <\/p>\n

<\/span><\/span><\/span>x<\/span>3<\/span>c<\/span><\/span><\/span><\/span> <\/p>\n

<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u3002\u65ad\u5f00\u6240\u4ee5\u548cc\u76f8\u8fde\u7684\u8fb9，\u5982\u679ca\u548cb\u5728\u540c\u4e00\u4e2a\u8fde\u901a\u533a\u57df，\u5219\u6709\u516c\u5171\u8fb9\u3002\u7528\u5e76\u67e5\u96c6\u770b\u662f\u5426\u5728\u540c\u4e00\u4e2a\u8fde\u901a\u533a\u57df\u3002 \u65f6\u95f4\u590d\u6742\u5ea6： O(nnlogn)\u3002 \u679a\u4e3ec，\u65f6\u95f4\u590d\u6742\u5ea6O(n)；\u679a\u4e3eab，\u65f6\u95f4\u590d\u6742\u5ea6O(n)\u3002\u67e5\u516c\u5171\u8def\u5f84O(logn)\u3002<\/p>\n

\u5e76\u96c6\u67e5\u627e<\/h2>\n

class<\/span> CNeiBo<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nstatic<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span> Two<\/span>(<\/span>int<\/span> n,<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> edges,<\/span> bool<\/span> bDirect,<\/span> int<\/span> iBase =<\/span> 0<\/span>)<\/span>
\n{<\/span>
\nvector<<\/span>vector<<\/span>int<\/span>>><\/span> vNeiBo<\/span>(<\/span>n)<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> v :<\/span> edges)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase)<\/span>;<\/span>
\nif<\/span> (<\/span>!<\/span>bDirect)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> vNeiBo;<\/span>
\n}<\/span>
\nstatic<\/span> vector<<\/span>vector<<\/span>std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span> Three<\/span>(<\/span>int<\/span> n,<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> edges,<\/span> bool<\/span> bDirect,<\/span> int<\/span> iBase =<\/span> 0<\/span>)<\/span>
\n{<\/span>
\nvector<<\/span>vector<<\/span>std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span> vNeiBo<\/span>(<\/span>n)<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> v :<\/span> edges)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase,<\/span> v[<\/span>2<\/span>]<\/span>)<\/span>;<\/span>
\nif<\/span> (<\/span>!<\/span>bDirect)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase,<\/span> v[<\/span>2<\/span>]<\/span>)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> vNeiBo;<\/span>
\n}<\/span>
\n}<\/span>;<\/span>
\nclass<\/span> CUnionFind<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nCUnionFind<\/span>(<\/span>int<\/span> iSize)<\/span> :<\/span>m_vNodeToRegion<\/span>(<\/span>iSize)<\/span>
\n{<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> iSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nm_vNodeToRegion[<\/span>i]<\/span> =<\/span> i;<\/span>
\n}<\/span>
\nm_iConnetRegionCount =<\/span> iSize;<\/span>
\n}<\/span>
\nCUnionFind<\/span>(<\/span>vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> vNeiBo)<\/span>:<\/span>CUnionFind<\/span>(<\/span>vNeiBo.<\/span>size<\/span>(<\/span>)<\/span>)<\/span>
\n{<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> vNeiBo.<\/span>size<\/span>(<\/span>)<\/span>;<\/span> i++<\/span>)<\/span> {<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> n :<\/span> vNeiBo[<\/span>i]<\/span>)<\/span> {<\/span>
\nUnion<\/span>(<\/span>i,<\/span> n)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\n}<\/span>
\nint<\/span> GetConnectRegionIndex<\/span>(<\/span>int<\/span> iNode)<\/span>
\n{<\/span>
\nint<\/span>&<\/span> iConnectNO =<\/span> m_vNodeToRegion[<\/span>iNode]<\/span>;<\/span>
\nif<\/span> (<\/span>iNode ==<\/span> iConnectNO)<\/span>
\n{<\/span>
\nreturn<\/span> iNode;<\/span>
\n}<\/span>
\nreturn<\/span> iConnectNO =<\/span> GetConnectRegionIndex<\/span>(<\/span>iConnectNO)<\/span>;<\/span>
\n}<\/span>
\nvoid<\/span> Union<\/span>(<\/span>int<\/span> iNode1,<\/span> int<\/span> iNode2)<\/span>
\n{<\/span>
\nconst<\/span> int<\/span> iConnectNO1 =<\/span> GetConnectRegionIndex<\/span>(<\/span>iNode1)<\/span>;<\/span>
\nconst<\/span> int<\/span> iConnectNO2 =<\/span> GetConnectRegionIndex<\/span>(<\/span>iNode2)<\/span>;<\/span>
\nif<\/span> (<\/span>iConnectNO1 ==<\/span> iConnectNO2)<\/span>
\n{<\/span>
\nreturn<\/span>;<\/span>
\n}<\/span>
\nm_iConnetRegionCount—<\/span>;<\/span>
\nif<\/span> (<\/span>iConnectNO1 ><\/span> iConnectNO2)<\/span>
\n{<\/span>
\nUnionConnect<\/span>(<\/span>iConnectNO1,<\/span> iConnectNO2)<\/span>;<\/span>
\n}<\/span>
\nelse<\/span>
\n{<\/span>
\nUnionConnect<\/span>(<\/span>iConnectNO2,<\/span> iConnectNO1)<\/span>;<\/span>
\n}<\/span>
\n}<\/span><\/p>\n

bool<\/span> IsConnect<\/span>(<\/span>int<\/span> iNode1,<\/span> int<\/span> iNode2)<\/span>
\n{<\/span>
\nreturn<\/span> GetConnectRegionIndex<\/span>(<\/span>iNode1)<\/span> ==<\/span> GetConnectRegionIndex<\/span>(<\/span>iNode2)<\/span>;<\/span>
\n}<\/span>
\nint<\/span> GetConnetRegionCount<\/span>(<\/span>)<\/span>const<\/span>
\n{<\/span>
\nreturn<\/span> m_iConnetRegionCount;<\/span>
\n}<\/span>
\nvector<<\/span>int<\/span>><\/span> GetNodeCountOfRegion<\/span>(<\/span>)<\/span>\/\/\u5404\u8054\u901a\u533a\u57df\u7684\u8282\u70b9\u6570\u91cf<\/span>
\n{<\/span>
\nconst<\/span> int<\/span> iNodeSize =<\/span> m_vNodeToRegion.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\nvector<<\/span>int<\/span>><\/span> vRet<\/span>(<\/span>iNodeSize)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> iNodeSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nvRet[<\/span>GetConnectRegionIndex<\/span>(<\/span>i)<\/span>]<\/span>++<\/span>;<\/span>
\n}<\/span>
\nreturn<\/span> vRet;<\/span>
\n}<\/span>
\nstd::<\/span>unordered_map<<\/span>int<\/span>,<\/span> vector<<\/span>int<\/span>>><\/span> GetNodeOfRegion<\/span>(<\/span>)<\/span>
\n{<\/span>
\nstd::<\/span>unordered_map<<\/span>int<\/span>,<\/span> vector<<\/span>int<\/span>>><\/span> ret;<\/span>
\nconst<\/span> int<\/span> iNodeSize =<\/span> m_vNodeToRegion.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> iNodeSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nret[<\/span>GetConnectRegionIndex<\/span>(<\/span>i)<\/span>]<\/span>.<\/span>emplace_back<\/span>(<\/span>i)<\/span>;<\/span>
\n}<\/span>
\nreturn<\/span> ret;<\/span>
\n}<\/span>
\nprivate<\/span>:<\/span>
\nvoid<\/span> UnionConnect<\/span>(<\/span>int<\/span> iFrom,<\/span> int<\/span> iTo)<\/span>
\n{<\/span>
\nm_vNodeToRegion[<\/span>iFrom]<\/span> =<\/span> iTo;<\/span>
\n}<\/span>
\nvector<<\/span>int<\/span>><\/span> m_vNodeToRegion;<\/span>\/\/\u5404\u70b9\u6240\u5728\u8054\u901a\u533a\u57df\u7684\u7d22\u5f15,\u672c\u8054\u901a\u533a\u57df\u4efb\u610f\u4e00\u70b9\u7684\u7d22\u5f15，\u4e3a\u4e86\u589e\u52a0\u53ef\u7406\u89e3\u6027，\u7528\u6700\u5c0f\u7d22\u5f15<\/span>
\nint<\/span> m_iConnetRegionCount;<\/span>
\n}<\/span>;<\/span><\/p>\n

class<\/span> CParents<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nCParents<\/span>(<\/span>vector<<\/span>int<\/span>><\/span>&<\/span> vParent,<\/span> const<\/span> vector<<\/span>int<\/span>><\/span>&<\/span> vLeve)<\/span>:<\/span>m_vLeve<\/span>(<\/span>vLeve)<\/span>
\n{<\/span>
\nconst<\/span> int<\/span> iMaxLeve =<\/span> *<\/span>std::<\/span>max_element<\/span>(<\/span>vLeve.<\/span>begin<\/span>(<\/span>)<\/span>,<\/span> vLeve.<\/span>end<\/span>(<\/span>)<\/span>)<\/span>;<\/span>
\nint<\/span> iBitNum =<\/span> 0<\/span>;<\/span>
\nfor<\/span> (<\/span>;<\/span> (<\/span>1<\/span> <<<\/span> iBitNum)<\/span> <<\/span> iMaxLeve;<\/span> iBitNum++<\/span>)<\/span>;<\/span>
\nconst<\/span> int<\/span> n =<\/span> vParent.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\nm_vParents.<\/span>assign<\/span>(<\/span>iBitNum+<\/span>1<\/span>,<\/span> vector<\/span><<\/span>int<\/span>><\/span><\/span><\/span>(<\/span>n,<\/span> –<\/span>1<\/span>)<\/span>)<\/span>;<\/span>
\nm_vParents[<\/span>0<\/span>]<\/span> =<\/span> vParent;<\/span>
\n\/\/\u6811\u4e0a\u500d\u589e<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 1<\/span>;<\/span> i <<\/span> m_vParents.<\/span>size<\/span>(<\/span>)<\/span>;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nfor<\/span> (<\/span>int<\/span> j =<\/span> 0<\/span>;<\/span> j <<\/span> n;<\/span> j++<\/span>)<\/span>
\n{<\/span>
\nconst<\/span> int<\/span> iPre =<\/span> m_vParents[<\/span>i –<\/span> 1<\/span>]<\/span>[<\/span>j]<\/span>;<\/span>
\nif<\/span> (<\/span>–<\/span>1<\/span> !=<\/span> iPre)<\/span>
\n{<\/span>
\nm_vParents[<\/span>i]<\/span>[<\/span>j]<\/span> =<\/span> m_vParents[<\/span>i –<\/span> 1<\/span>]<\/span>[<\/span>iPre]<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\n}<\/span>
\n}<\/span>
\nint<\/span> GetParent<\/span>(<\/span>int<\/span> iNode,<\/span> int<\/span> iLeve)<\/span>const<\/span>
\n{<\/span>
\nint<\/span> iParent =<\/span> iNode;<\/span>
\nfor<\/span> (<\/span>int<\/span> iBit =<\/span> 0<\/span>;<\/span> iBit <<\/span> m_vParents.<\/span>size<\/span>(<\/span>)<\/span>;<\/span> iBit++<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>–<\/span>1<\/span> ==<\/span> iParent)<\/span>
\n{<\/span>
\nreturn<\/span> iParent;<\/span>
\n}<\/span>
\nif<\/span> (<\/span>iLeve &<\/span> (<\/span>1<\/span> <<<\/span> iBit)<\/span>)<\/span>
\n{<\/span>
\niParent =<\/span> m_vParents[<\/span>iBit]<\/span>[<\/span>iParent]<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> iParent;<\/span>
\n}<\/span>
\nint<\/span> GetPublicParent<\/span>(<\/span>int<\/span> iNode1,<\/span> int<\/span> iNode2)<\/span>const<\/span>
\n{<\/span>
\nint<\/span> leve0 =<\/span> m_vLeve[<\/span>iNode1]<\/span>;<\/span>
\nint<\/span> leve1 =<\/span> m_vLeve[<\/span>iNode2]<\/span>;<\/span>
\nif<\/span> (<\/span>leve0 <<\/span> leve1)<\/span>
\n{<\/span>
\niNode2 =<\/span> GetParent<\/span>(<\/span>iNode2,<\/span> leve1 –<\/span> leve0)<\/span>;<\/span>
\nleve1 =<\/span> leve0;<\/span>
\n}<\/span>
\nelse<\/span>
\n{<\/span>
\niNode1 =<\/span> GetParent<\/span>(<\/span>iNode1,<\/span> leve0 –<\/span> leve1)<\/span>;<\/span>
\nleve0 =<\/span> leve1;<\/span>
\n}<\/span>
\n\/\/\u4e8c\u5206\u67e5\u627e<\/span>
\nint<\/span> left =<\/span> –<\/span>1<\/span>,<\/span> r =<\/span> leve0;<\/span>
\nwhile<\/span> (<\/span>r –<\/span> left ><\/span> 1<\/span>)<\/span>
\n{<\/span>
\nconst<\/span> auto<\/span> mid =<\/span> left +<\/span> (<\/span>r –<\/span> left)<\/span> \/<\/span> 2<\/span>;<\/span>
\nconst<\/span> int<\/span> iParent0 =<\/span> GetParent<\/span>(<\/span>iNode1,<\/span> mid)<\/span>;<\/span>
\nconst<\/span> int<\/span> iParent1 =<\/span> GetParent<\/span>(<\/span>iNode2,<\/span> mid)<\/span>;<\/span>
\nif<\/span> (<\/span>iParent0 ==<\/span> iParent1)<\/span>
\n{<\/span>
\nr =<\/span> mid;<\/span>
\n}<\/span>
\nelse<\/span>
\n{<\/span>
\nleft =<\/span> mid;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> GetParent<\/span>(<\/span>iNode1,<\/span> r)<\/span>;<\/span>
\n}<\/span>
\nprotected<\/span>:<\/span>
\nvector<<\/span>vector<<\/span>int<\/span>>><\/span> m_vParents;<\/span>
\nconst<\/span> vector<<\/span>int<\/span>><\/span> m_vLeve;<\/span>
\n}<\/span>;<\/span><\/p>\n

class<\/span> Solution<\/span> {<\/span>
\npublic<\/span>:<\/span>
\nvector<<\/span>int<\/span>><\/span> countPairsOfConnectableServers<\/span>(<\/span>vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> edges,<\/span> int<\/span> signalSpeed)<\/span> {<\/span>
\nm_c =<\/span> edges.<\/span>size<\/span>(<\/span>)<\/span> +<\/span> 1<\/span>;<\/span>
\nm_vDisToRoot.<\/span>resize<\/span>(<\/span>m_c)<\/span>;<\/span>
\nm_vParent.<\/span>resize<\/span>(<\/span>m_c)<\/span>;<\/span>
\nm_vLeve.<\/span>resize<\/span>(<\/span>m_c)<\/span>;<\/span>
\nauto<\/span> neiBo =<\/span> CNeiBo<\/span>::<\/span>Three<\/span>(<\/span>m_c,<\/span> edges,<\/span> false<\/span>,<\/span> 0<\/span>)<\/span>;<\/span>
\nDFS<\/span>(<\/span>neiBo,<\/span> 0<\/span>,<\/span> –<\/span>1<\/span>,<\/span> 0<\/span>,<\/span>0<\/span>)<\/span>;<\/span>
\nCParents par<\/span>(<\/span>m_vParent,<\/span>m_vLeve)<\/span>;<\/span>
\nvector<<\/span>int<\/span>><\/span> vRet<\/span>(<\/span>m_c)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> c =<\/span> 0<\/span>;<\/span> c <<\/span> m_c;<\/span> c++<\/span>)<\/span>
\n{<\/span>
\nCUnionFind uf<\/span>(<\/span>m_c)<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> v :<\/span> edges)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>(<\/span>v[<\/span>0<\/span>]<\/span> ==<\/span> c)<\/span> ||<\/span> (<\/span>v[<\/span>1<\/span>]<\/span> ==<\/span> c)<\/span>)<\/span>
\n{<\/span>
\ncontinue<\/span>;<\/span>
\n}<\/span>
\nuf.<\/span>Union<\/span>(<\/span>v[<\/span>0<\/span>]<\/span>,<\/span> v[<\/span>1<\/span>]<\/span>)<\/span>;<\/span>
\n}<\/span>
\nvector<<\/span>int<\/span>><\/span> vRegionCnt<\/span>(<\/span>m_c)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> ab =<\/span> 0<\/span>;<\/span> ab <<\/span> m_c;<\/span> ab++<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>ab ==<\/span> c )<\/span>
\n{<\/span>
\ncontinue<\/span>;<\/span>
\n}<\/span>
\nconst<\/span> int<\/span> pub =<\/span> par.<\/span>GetPublicParent<\/span>(<\/span>ab,<\/span> c)<\/span>;<\/span>
\nconst<\/span> int<\/span> len =<\/span> m_vDisToRoot[<\/span>ab]<\/span> +<\/span> m_vDisToRoot[<\/span>c]<\/span> –<\/span> 2<\/span> *<\/span> m_vDisToRoot[<\/span>pub]<\/span>;<\/span>
\nif<\/span> (<\/span>0<\/span> !=<\/span> len %<\/span> signalSpeed)<\/span>
\n{<\/span>
\ncontinue<\/span>;<\/span>
\n}<\/span>
\nvRegionCnt[<\/span>uf.<\/span>GetConnectRegionIndex<\/span>(<\/span>ab)<\/span>]<\/span>++<\/span>;<\/span>
\n}<\/span>
\nint<\/span>&<\/span>iRet =<\/span> vRet[<\/span>c]<\/span>;<\/span>
\nconst<\/span> int<\/span> total =<\/span> std::<\/span>accumulate<\/span>(<\/span>vRegionCnt.<\/span>begin<\/span>(<\/span>)<\/span>,<\/span> vRegionCnt.<\/span>end<\/span>(<\/span>)<\/span>,<\/span> 0<\/span>)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> c1 =<\/span> 0<\/span>;<\/span> c1 <<\/span> m_c;<\/span> c1++<\/span>)<\/span>
\n{<\/span>
\niRet +=<\/span> vRegionCnt[<\/span>c1]<\/span> *<\/span> (<\/span>total –<\/span> vRegionCnt[<\/span>c1]<\/span>)<\/span>;<\/span>
\n}<\/span>
\niRet \/=<\/span> 2<\/span>;<\/span>
\n}<\/span>
\nreturn<\/span> vRet;<\/span>
\n}<\/span>
\nvoid<\/span> DFS<\/span>(<\/span>vector<<\/span>vector<<\/span>std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span>&<\/span> neiBo,<\/span> int<\/span> cur,<\/span> int<\/span> par,<\/span>int<\/span> leve,<\/span>int<\/span> dis)<\/span>
\n{<\/span>
\nm_vDisToRoot[<\/span>cur]<\/span> =<\/span>dis;<\/span>
\nm_vParent[<\/span>cur]<\/span> =<\/span> par;<\/span>
\nm_vLeve[<\/span>cur]<\/span> =<\/span> leve;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> [<\/span>next,<\/span>len]<\/span> :<\/span> neiBo[<\/span>cur]<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>next ==<\/span> par)<\/span>
\n{<\/span>
\ncontinue<\/span>;<\/span>
\n}<\/span>
\nDFS<\/span>(<\/span>neiBo,<\/span> next,<\/span> cur,<\/span>leve+<\/span>1<\/span>,<\/span>dis+<\/span>len)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nvector<<\/span>int<\/span>><\/span> m_vDisToRoot,<\/span>m_vParent,<\/span>m_vLeve;<\/span>
\nint<\/span> m_c;<\/span>
\n}<\/span>;<\/span><\/p>\n

\u6d4b\u8bd5\u7528\u4f8b<\/h3>\n

template<\/span><<\/span>class<\/span> T<\/span>,<\/span>class<\/span> T2<\/span>><\/span>
\nvoid<\/span> Assert<\/span>(<\/span>const<\/span> T&<\/span> t1,<\/span> const<\/span> T2&<\/span> t2)<\/span>
\n{<\/span>
\nassert<\/span>(<\/span>t1 ==<\/span> t2)<\/span>;<\/span>
\n}<\/span><\/p>\n

template<\/span><<\/span>class<\/span> T<\/span>><\/span>
\nvoid<\/span> Assert<\/span>(<\/span>const<\/span> vector<<\/span>T><\/span>&<\/span> v1,<\/span> const<\/span> vector<<\/span>T><\/span>&<\/span> v2)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>v1.<\/span>size<\/span>(<\/span>)<\/span> !=<\/span> v2.<\/span>size<\/span>(<\/span>)<\/span>)<\/span>
\n{<\/span>
\nassert<\/span>(<\/span>false<\/span>)<\/span>;<\/span>
\nreturn<\/span>;<\/span>
\n}<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> v1.<\/span>size<\/span>(<\/span>)<\/span>;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nAssert<\/span>(<\/span>v1[<\/span>i]<\/span>,<\/span> v2[<\/span>i]<\/span>)<\/span>;<\/span>
\n}<\/span><\/p>\n

}<\/span><\/p>\n

int<\/span> main<\/span>(<\/span>)<\/span>
\n{<\/span>
\nvector<<\/span>vector<<\/span>int<\/span>>><\/span> edges;<\/span>
\nint<\/span> signalSpeed;<\/span>
\n{<\/span>
\nSolution sln;<\/span>
\nedges =<\/span> {<\/span> }<\/span>,<\/span> signalSpeed =<\/span> 1<\/span>;<\/span>
\nauto<\/span> res =<\/span> sln.<\/span>countPairsOfConnectableServers<\/span>(<\/span>edges,<\/span> signalSpeed)<\/span>;<\/span>
\nAssert<\/span>(<\/span>{<\/span> 0<\/span> }<\/span>,<\/span> res)<\/span>;<\/span>
\n}<\/span>
\n{<\/span>
\nSolution sln;<\/span>
\nedges =<\/span> {<\/span> {<\/span>0<\/span>,<\/span>1<\/span>,<\/span>1<\/span>}<\/span> }<\/span>,<\/span> signalSpeed =<\/span> 1<\/span>;<\/span>
\nauto<\/span> res =<\/span> sln.<\/span>countPairsOfConnectableServers<\/span>(<\/span>edges,<\/span> signalSpeed)<\/span>;<\/span>
\nAssert<\/span>(<\/span>{<\/span> 0<\/span>,<\/span>0<\/span> }<\/span>,<\/span> res)<\/span>;<\/span>
\n}<\/span>
\n{<\/span>
\nSolution sln;<\/span>
\nedges =<\/span> {<\/span> {<\/span>0<\/span>,<\/span>1<\/span>,<\/span>1<\/span>}<\/span>,<\/span>{<\/span>1<\/span>,<\/span>2<\/span>,<\/span>1<\/span>}<\/span> }<\/span>,<\/span> signalSpeed =<\/span> 1<\/span>;<\/span>
\nauto<\/span> res =<\/span> sln.<\/span>countPairsOfConnectableServers<\/span>(<\/span>edges,<\/span> signalSpeed)<\/span>;<\/span>
\nAssert<\/span>(<\/span>{<\/span> 0<\/span>,<\/span>1<\/span>,<\/span>0<\/span> }<\/span>,<\/span> res)<\/span>;<\/span>
\n}<\/span>
\n{<\/span>
\nSolution sln;<\/span>
\nedges =<\/span> {<\/span> {<\/span>0<\/span>,<\/span>1<\/span>,<\/span>1<\/span>}<\/span>,<\/span>{<\/span>1<\/span>,<\/span>2<\/span>,<\/span>5<\/span>}<\/span>,<\/span>{<\/span>2<\/span>,<\/span>3<\/span>,<\/span>13<\/span>}<\/span>,<\/span>{<\/span>3<\/span>,<\/span>4<\/span>,<\/span>9<\/span>}<\/span>,<\/span>{<\/span>4<\/span>,<\/span>5<\/span>,<\/span>2<\/span>}<\/span> }<\/span>,<\/span> signalSpeed =<\/span> 1<\/span>;<\/span>
\nauto<\/span> res =<\/span> sln.<\/span>countPairsOfConnectableServers<\/span>(<\/span>edges,<\/span> signalSpeed)<\/span>;<\/span>
\nAssert<\/span>(<\/span>{<\/span> 0<\/span>,<\/span>4<\/span>,<\/span>6<\/span>,<\/span>6<\/span>,<\/span>4<\/span>,<\/span>0<\/span> }<\/span> ,<\/span> res)<\/span>;<\/span>
\n}<\/span>
\n{<\/span>
\nSolution sln;<\/span>
\nedges =<\/span> {<\/span> {<\/span>0<\/span>,<\/span>6<\/span>,<\/span>3<\/span>}<\/span>,<\/span>{<\/span>6<\/span>,<\/span>5<\/span>,<\/span>3<\/span>}<\/span>,<\/span>{<\/span>0<\/span>,<\/span>3<\/span>,<\/span>1<\/span>}<\/span>,<\/span>{<\/span>3<\/span>,<\/span>2<\/span>,<\/span>7<\/span>}<\/span>,<\/span>{<\/span>3<\/span>,<\/span>1<\/span>,<\/span>6<\/span>}<\/span>,<\/span>{<\/span>3<\/span>,<\/span>4<\/span>,<\/span>2<\/span>}<\/span> }<\/span>,<\/span> signalSpeed =<\/span> 3<\/span>;<\/span>
\nauto<\/span> res =<\/span> sln.<\/span>countPairsOfConnectableServers<\/span>(<\/span>edges,<\/span> signalSpeed)<\/span>;<\/span>
\nAssert<\/span>(<\/span>{<\/span> 2<\/span>,<\/span>0<\/span>,<\/span>0<\/span>,<\/span>0<\/span>,<\/span>0<\/span>,<\/span>0<\/span>,<\/span>2<\/span> }<\/span>,<\/span> res)<\/span>;<\/span>
\n}<\/span>
\n}<\/span><\/p>\n

\u6362\u6839\u6cd5DFS<\/h2>\n

\u6811\u4e2d\u5220\u9664\u4e00\u4e2a\u8282\u70b9，\u5219\u5404\u5b69\u5b50\u5404\u4e00\u4e2a\u8fde\u901a\u533a\u57df，\u9664\u81ea\u5df1\u53ca\u540e\u4ee3\u5916\u4e00\u4e2a\u533a\u57df\u3002\u5982\u679c\u8fd9\u4e2a\u8282\u70b9\u662f\u6839，\u5219\u7b80\u5355\u5f97\u591a\u3002\u5404\u5b69\u5b50\u4e00\u4e2a\u8fde\u901a\u533a\u57df\u3002 DSF(cur) \u8fd4\u56de\u81ea\u5df1\u53ca\u5b50\u5b59\u5230\u5f53\u524d\u6839\u8282\u70b9\u8ddd\u79bb\u662fsignalSpeed \u500d\u7684\u8282\u70b9\u6570\u91cf\u3002\u4ee4\u5f53\u524d\u6839\u8282\u70b9\u5404\u5b69\u5b50\u7684\u8fd4\u56de\u503c\u662f{i1,i2, <\/p>\n

\u22ef <\/p>\n

\\\\cdots <\/p>\n

<\/span><\/span>\u22ef<\/span><\/span><\/span><\/span><\/span>,im} \u3002i1*i2+(i1+i2)*i3 <\/p>\n

\u22ef <\/p>\n

\\\\cdots <\/p>\n

<\/span><\/span>\u22ef<\/span><\/span><\/span><\/span><\/span> +(I1+i2+ <\/p>\n

\u2026 <\/p>\n

\\\\dots <\/p>\n

<\/span><\/span>\u2026<\/span><\/span><\/span><\/span><\/span> + i <\/p>\n

m <\/p>\n

\u2212 <\/p>\n

1 <\/p>\n

_{m-1} <\/p>\n

<\/span><\/span><\/span><\/span>m<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>)*im\u3002\u8fd9\u6837\u4e0d\u5fc5\u9664\u4ee5\u4e8c\u3002 a<b ，\u8868\u793aa !=b ，(a,b)\u548c(b,a)\u53ea\u53d6\u4e00\u4e2a\u3002<\/p>\n

class<\/span> CNeiBo<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nstatic<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span> Two<\/span>(<\/span>int<\/span> n,<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> edges,<\/span> bool<\/span> bDirect,<\/span> int<\/span> iBase =<\/span> 0<\/span>)<\/span>
\n{<\/span>
\nvector<<\/span>vector<<\/span>int<\/span>>><\/span> vNeiBo<\/span>(<\/span>n)<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> v :<\/span> edges)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase)<\/span>;<\/span>
\nif<\/span> (<\/span>!<\/span>bDirect)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> vNeiBo;<\/span>
\n}<\/span>
\nstatic<\/span> vector<<\/span>vector<<\/span>std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span> Three<\/span>(<\/span>int<\/span> n,<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> edges,<\/span> bool<\/span> bDirect,<\/span> int<\/span> iBase =<\/span> 0<\/span>)<\/span>
\n{<\/span>
\nvector<<\/span>vector<<\/span>std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span> vNeiBo<\/span>(<\/span>n)<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> v :<\/span> edges)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase,<\/span> v[<\/span>2<\/span>]<\/span>)<\/span>;<\/span>
\nif<\/span> (<\/span>!<\/span>bDirect)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase,<\/span> v[<\/span>2<\/span>]<\/span>)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> vNeiBo;<\/span>
\n}<\/span>
\n}<\/span>;<\/span><\/p>\n

class<\/span> Solution<\/span> {<\/span>
\npublic<\/span>:<\/span>
\nvector<<\/span>int<\/span>><\/span> countPairsOfConnectableServers<\/span>(<\/span>vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> edges,<\/span> int<\/span> signalSpeed)<\/span> {<\/span>
\nm_c =<\/span> edges.<\/span>size<\/span>(<\/span>)<\/span> +<\/span> 1<\/span>;<\/span>
\nm_iSignalSpeed =<\/span> signalSpeed;<\/span>
\nauto<\/span> neiBo =<\/span> CNeiBo<\/span>::<\/span>Three<\/span>(<\/span>m_c,<\/span> edges,<\/span> false<\/span>,<\/span> 0<\/span>)<\/span>;<\/span>
\nvector<<\/span>int<\/span>><\/span> vRet<\/span>(<\/span>m_c)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> c =<\/span> 0<\/span>;<\/span> c <<\/span> m_c;<\/span> c++<\/span>)<\/span>
\n{<\/span>
\nint<\/span>&<\/span> iRet =<\/span> vRet[<\/span>c]<\/span>;<\/span>
\nint<\/span> left =<\/span> 0<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> [<\/span>next,<\/span> len]<\/span> :<\/span> neiBo[<\/span>c]<\/span>)<\/span>
\n{<\/span>
\nint<\/span> cur =<\/span> DFS<\/span>(<\/span>neiBo,<\/span> next,<\/span> c,<\/span> len)<\/span>;<\/span>
\niRet +=<\/span> left *<\/span> cur;<\/span>
\nleft +=<\/span> cur;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> vRet;<\/span>
\n}<\/span>
\nint<\/span> DFS<\/span>(<\/span>vector<<\/span>vector<<\/span>std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span>&<\/span> neiBo,<\/span> int<\/span> cur,<\/span> int<\/span> par,<\/span>int<\/span> dis)<\/span>
\n{<\/span>
\nint<\/span> iRet =<\/span> (<\/span>0<\/span> ==<\/span>dis %<\/span> m_iSignalSpeed)<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> [<\/span>next,<\/span>len]<\/span> :<\/span> neiBo[<\/span>cur]<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>next ==<\/span> par)<\/span>
\n{<\/span>
\ncontinue<\/span>;<\/span>
\n}<\/span>
\niRet +=<\/span>DFS<\/span>(<\/span>neiBo,<\/span> next,<\/span> cur,<\/span>dis+<\/span>len)<\/span>;<\/span>
\n}<\/span>
\nreturn<\/span> iRet;<\/span>
\n}<\/span>
\nint<\/span> m_iSignalSpeed;<\/span>
\nint<\/span> m_c;<\/span>
\n}<\/span>;<\/span><\/p>\n

\u5272\u70b9<\/h2>\n

\u672c\u89e3\u6cd5\u8fc7\u4e8e\u590d\u6742，\u9664\u975e\u7528\u4e86\u63d0\u524d\u5c01\u88c5\u597d\u7684\u5272\u70b9\u6269\u5c55\u7c7b，\u5426\u5219\u88ab\u4f7f\u7528\u3002<\/p>\n

class<\/span> CNeiBo<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nstatic<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span> Two<\/span>(<\/span>int<\/span> n,<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> edges,<\/span> bool<\/span> bDirect,<\/span> int<\/span> iBase =<\/span> 0<\/span>)<\/span>
\n{<\/span>
\nvector<<\/span>vector<<\/span>int<\/span>>><\/span> vNeiBo<\/span>(<\/span>n)<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> v :<\/span> edges)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase)<\/span>;<\/span>
\nif<\/span> (<\/span>!<\/span>bDirect)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> vNeiBo;<\/span>
\n}<\/span>
\nstatic<\/span> vector<<\/span>vector<<\/span>std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span> Three<\/span>(<\/span>int<\/span> n,<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> edges,<\/span> bool<\/span> bDirect,<\/span> int<\/span> iBase =<\/span> 0<\/span>)<\/span>
\n{<\/span>
\nvector<<\/span>vector<<\/span>std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span> vNeiBo<\/span>(<\/span>n)<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> v :<\/span> edges)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase,<\/span> v[<\/span>2<\/span>]<\/span>)<\/span>;<\/span>
\nif<\/span> (<\/span>!<\/span>bDirect)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase,<\/span> v[<\/span>2<\/span>]<\/span>)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> vNeiBo;<\/span>
\n}<\/span>
\n}<\/span>;<\/span>
\nclass<\/span> CUnionFind<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nCUnionFind<\/span>(<\/span>int<\/span> iSize)<\/span> :<\/span>m_vNodeToRegion<\/span>(<\/span>iSize)<\/span>
\n{<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> iSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nm_vNodeToRegion[<\/span>i]<\/span> =<\/span> i;<\/span>
\n}<\/span>
\nm_iConnetRegionCount =<\/span> iSize;<\/span>
\n}<\/span>
\nCUnionFind<\/span>(<\/span>vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> vNeiBo)<\/span>:<\/span>CUnionFind<\/span>(<\/span>vNeiBo.<\/span>size<\/span>(<\/span>)<\/span>)<\/span>
\n{<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> vNeiBo.<\/span>size<\/span>(<\/span>)<\/span>;<\/span> i++<\/span>)<\/span> {<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> n :<\/span> vNeiBo[<\/span>i]<\/span>)<\/span> {<\/span>
\nUnion<\/span>(<\/span>i,<\/span> n)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\n}<\/span>
\nint<\/span> GetConnectRegionIndex<\/span>(<\/span>int<\/span> iNode)<\/span>
\n{<\/span>
\nint<\/span>&<\/span> iConnectNO =<\/span> m_vNodeToRegion[<\/span>iNode]<\/span>;<\/span>
\nif<\/span> (<\/span>iNode ==<\/span> iConnectNO)<\/span>
\n{<\/span>
\nreturn<\/span> iNode;<\/span>
\n}<\/span>
\nreturn<\/span> iConnectNO =<\/span> GetConnectRegionIndex<\/span>(<\/span>iConnectNO)<\/span>;<\/span>
\n}<\/span>
\nvoid<\/span> Union<\/span>(<\/span>int<\/span> iNode1,<\/span> int<\/span> iNode2)<\/span>
\n{<\/span>
\nconst<\/span> int<\/span> iConnectNO1 =<\/span> GetConnectRegionIndex<\/span>(<\/span>iNode1)<\/span>;<\/span>
\nconst<\/span> int<\/span> iConnectNO2 =<\/span> GetConnectRegionIndex<\/span>(<\/span>iNode2)<\/span>;<\/span>
\nif<\/span> (<\/span>iConnectNO1 ==<\/span> iConnectNO2)<\/span>
\n{<\/span>
\nreturn<\/span>;<\/span>
\n}<\/span>
\nm_iConnetRegionCount—<\/span>;<\/span>
\nif<\/span> (<\/span>iConnectNO1 ><\/span> iConnectNO2)<\/span>
\n{<\/span>
\nUnionConnect<\/span>(<\/span>iConnectNO1,<\/span> iConnectNO2)<\/span>;<\/span>
\n}<\/span>
\nelse<\/span>
\n{<\/span>
\nUnionConnect<\/span>(<\/span>iConnectNO2,<\/span> iConnectNO1)<\/span>;<\/span>
\n}<\/span>
\n}<\/span><\/p>\n

bool<\/span> IsConnect<\/span>(<\/span>int<\/span> iNode1,<\/span> int<\/span> iNode2)<\/span>
\n{<\/span>
\nreturn<\/span> GetConnectRegionIndex<\/span>(<\/span>iNode1)<\/span> ==<\/span> GetConnectRegionIndex<\/span>(<\/span>iNode2)<\/span>;<\/span>
\n}<\/span>
\nint<\/span> GetConnetRegionCount<\/span>(<\/span>)<\/span>const<\/span>
\n{<\/span>
\nreturn<\/span> m_iConnetRegionCount;<\/span>
\n}<\/span>
\nvector<<\/span>int<\/span>><\/span> GetNodeCountOfRegion<\/span>(<\/span>)<\/span>\/\/\u5404\u8054\u901a\u533a\u57df\u7684\u8282\u70b9\u6570\u91cf<\/span>
\n{<\/span>
\nconst<\/span> int<\/span> iNodeSize =<\/span> m_vNodeToRegion.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\nvector<<\/span>int<\/span>><\/span> vRet<\/span>(<\/span>iNodeSize)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> iNodeSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nvRet[<\/span>GetConnectRegionIndex<\/span>(<\/span>i)<\/span>]<\/span>++<\/span>;<\/span>
\n}<\/span>
\nreturn<\/span> vRet;<\/span>
\n}<\/span>
\nstd::<\/span>unordered_map<<\/span>int<\/span>,<\/span> vector<<\/span>int<\/span>>><\/span> GetNodeOfRegion<\/span>(<\/span>)<\/span>
\n{<\/span>
\nstd::<\/span>unordered_map<<\/span>int<\/span>,<\/span> vector<<\/span>int<\/span>>><\/span> ret;<\/span>
\nconst<\/span> int<\/span> iNodeSize =<\/span> m_vNodeToRegion.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> iNodeSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nret[<\/span>GetConnectRegionIndex<\/span>(<\/span>i)<\/span>]<\/span>.<\/span>emplace_back<\/span>(<\/span>i)<\/span>;<\/span>
\n}<\/span>
\nreturn<\/span> ret;<\/span>
\n}<\/span>
\nprivate<\/span>:<\/span>
\nvoid<\/span> UnionConnect<\/span>(<\/span>int<\/span> iFrom,<\/span> int<\/span> iTo)<\/span>
\n{<\/span>
\nm_vNodeToRegion[<\/span>iFrom]<\/span> =<\/span> iTo;<\/span>
\n}<\/span>
\nvector<<\/span>int<\/span>><\/span> m_vNodeToRegion;<\/span>\/\/\u5404\u70b9\u6240\u5728\u8054\u901a\u533a\u57df\u7684\u7d22\u5f15,\u672c\u8054\u901a\u533a\u57df\u4efb\u610f\u4e00\u70b9\u7684\u7d22\u5f15，\u4e3a\u4e86\u589e\u52a0\u53ef\u7406\u89e3\u6027，\u7528\u6700\u5c0f\u7d22\u5f15<\/span>
\nint<\/span> m_iConnetRegionCount;<\/span>
\n}<\/span>;<\/span><\/p>\n

class<\/span> CParents<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nCParents<\/span>(<\/span>vector<<\/span>int<\/span>><\/span>&<\/span> vParent,<\/span> const<\/span> int<\/span> iMaxLeve)<\/span>
\n{<\/span>
\nint<\/span> iBitNum =<\/span> 0<\/span>;<\/span>
\nfor<\/span> (<\/span>;<\/span> (<\/span>1<\/span> <<<\/span> iBitNum)<\/span> <<\/span> iMaxLeve;<\/span> iBitNum++<\/span>)<\/span>;<\/span>
\nconst<\/span> int<\/span> n =<\/span> vParent.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\nm_vParents.<\/span>assign<\/span>(<\/span>iBitNum+<\/span>1<\/span>,<\/span> vector<\/span><<\/span>int<\/span>><\/span><\/span><\/span>(<\/span>n,<\/span> –<\/span>1<\/span>)<\/span>)<\/span>;<\/span>
\nm_vParents[<\/span>0<\/span>]<\/span> =<\/span> vParent;<\/span>
\n\/\/\u6811\u4e0a\u500d\u589e<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 1<\/span>;<\/span> i <<\/span> m_vParents.<\/span>size<\/span>(<\/span>)<\/span>;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nfor<\/span> (<\/span>int<\/span> j =<\/span> 0<\/span>;<\/span> j <<\/span> n;<\/span> j++<\/span>)<\/span>
\n{<\/span>
\nconst<\/span> int<\/span> iPre =<\/span> m_vParents[<\/span>i –<\/span> 1<\/span>]<\/span>[<\/span>j]<\/span>;<\/span>
\nif<\/span> (<\/span>–<\/span>1<\/span> !=<\/span> iPre)<\/span>
\n{<\/span>
\nm_vParents[<\/span>i]<\/span>[<\/span>j]<\/span> =<\/span> m_vParents[<\/span>i –<\/span> 1<\/span>]<\/span>[<\/span>iPre]<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\n}<\/span>
\n}<\/span>
\nint<\/span> GetParent<\/span>(<\/span>int<\/span> iNode,<\/span> int<\/span> iLeve)<\/span>const<\/span>
\n{<\/span>
\nint<\/span> iParent =<\/span> iNode;<\/span>
\nfor<\/span> (<\/span>int<\/span> iBit =<\/span> 0<\/span>;<\/span> iBit <<\/span> m_vParents.<\/span>size<\/span>(<\/span>)<\/span>;<\/span> iBit++<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>–<\/span>1<\/span> ==<\/span> iParent)<\/span>
\n{<\/span>
\nreturn<\/span> iParent;<\/span>
\n}<\/span>
\nif<\/span> (<\/span>iLeve &<\/span> (<\/span>1<\/span> <<<\/span> iBit)<\/span>)<\/span>
\n{<\/span>
\niParent =<\/span> m_vParents[<\/span>iBit]<\/span>[<\/span>iParent]<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> iParent;<\/span>
\n}<\/span>
\nprotected<\/span>:<\/span>
\nvector<<\/span>vector<<\/span>int<\/span>>><\/span> m_vParents;<\/span>
\n}<\/span>;<\/span><\/p>\n

class<\/span> C2Parents<\/span> :<\/span> CParents<\/span><\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nC2Parents<\/span>(<\/span>vector<<\/span>int<\/span>><\/span>&<\/span> vParent,<\/span> const<\/span> vector<<\/span>int<\/span>><\/span>&<\/span> vLeve)<\/span> :<\/span>m_vLeve<\/span>(<\/span>vLeve)<\/span>
\n,<\/span> CParents<\/span>(<\/span>vParent,<\/span>*<\/span>std::<\/span>max_element<\/span>(<\/span>vLeve.<\/span>begin<\/span>(<\/span>)<\/span>,<\/span> vLeve.<\/span>end<\/span>(<\/span>)<\/span>)<\/span>)<\/span>
\n{<\/span>
\n}<\/span>
\nint<\/span> GetPublicParent<\/span>(<\/span>int<\/span> iNode1,<\/span> int<\/span> iNode2)<\/span>const<\/span>
\n{<\/span>
\nint<\/span> leve0 =<\/span> m_vLeve[<\/span>iNode1]<\/span>;<\/span>
\nint<\/span> leve1 =<\/span> m_vLeve[<\/span>iNode2]<\/span>;<\/span>
\nif<\/span> (<\/span>leve0 <<\/span> leve1)<\/span>
\n{<\/span>
\niNode2 =<\/span> GetParent<\/span>(<\/span>iNode2,<\/span> leve1 –<\/span> leve0)<\/span>;<\/span>
\nleve1 =<\/span> leve0;<\/span>
\n}<\/span>
\nelse<\/span>
\n{<\/span>
\niNode1 =<\/span> GetParent<\/span>(<\/span>iNode1,<\/span> leve0 –<\/span> leve1)<\/span>;<\/span>
\nleve0 =<\/span> leve1;<\/span>
\n}<\/span>
\n\/\/\u4e8c\u5206\u67e5\u627e<\/span>
\nint<\/span> left =<\/span> –<\/span>1<\/span>,<\/span> r =<\/span> leve0;<\/span>
\nwhile<\/span> (<\/span>r –<\/span> left ><\/span> 1<\/span>)<\/span>
\n{<\/span>
\nconst<\/span> auto<\/span> mid =<\/span> left +<\/span> (<\/span>r –<\/span> left)<\/span> \/<\/span> 2<\/span>;<\/span>
\nconst<\/span> int<\/span> iParent0 =<\/span> GetParent<\/span>(<\/span>iNode1,<\/span> mid)<\/span>;<\/span>
\nconst<\/span> int<\/span> iParent1 =<\/span> GetParent<\/span>(<\/span>iNode2,<\/span> mid)<\/span>;<\/span>
\nif<\/span> (<\/span>iParent0 ==<\/span> iParent1)<\/span>
\n{<\/span>
\nr =<\/span> mid;<\/span>
\n}<\/span>
\nelse<\/span>
\n{<\/span>
\nleft =<\/span> mid;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> GetParent<\/span>(<\/span>iNode1,<\/span> r)<\/span>;<\/span>
\n}<\/span>
\nprotected<\/span>:<\/span><\/p>\n

vector<<\/span>vector<<\/span>int<\/span>>><\/span> m_vParents;<\/span>
\nconst<\/span> vector<<\/span>int<\/span>><\/span> m_vLeve;<\/span>
\n}<\/span>;<\/span><\/p>\n

class<\/span> CCutPointEx<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nCCutPointEx<\/span>(<\/span>const<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> vNeiB)<\/span> :<\/span> m_iSize<\/span>(<\/span>vNeiB.<\/span>size<\/span>(<\/span>)<\/span>)<\/span>
\n{<\/span>
\nm_vNodeToTime.<\/span>assign<\/span>(<\/span>m_iSize,<\/span> –<\/span>1<\/span>)<\/span>;<\/span>
\nm_vChildFirstEnd.<\/span>resize<\/span>(<\/span>m_iSize)<\/span>;<\/span>
\nm_vNodeToRegion.<\/span>assign<\/span>(<\/span>m_iSize,<\/span> –<\/span>1<\/span>)<\/span>;<\/span>
\nm_vCut.<\/span>assign<\/span>(<\/span>m_iSize,<\/span> false<\/span>)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> m_iSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>–<\/span>1<\/span> !=<\/span> m_vNodeToTime[<\/span>i]<\/span>)<\/span>
\n{<\/span>
\ncontinue<\/span>;<\/span>
\n}<\/span>
\ndfs<\/span>(<\/span>i,<\/span> –<\/span>1<\/span>,<\/span> vNeiB)<\/span>;<\/span>
\nm_iRegionCount++<\/span>;<\/span>
\n}<\/span>
\nm_vTimeToNode.<\/span>resize<\/span>(<\/span>m_iSize)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> m_iSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nm_vTimeToNode[<\/span>m_vNodeToTime[<\/span>i]<\/span>]<\/span> =<\/span> i;<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nbool<\/span> Visit<\/span>(<\/span>int<\/span> src,<\/span> int<\/span> dest,<\/span> int<\/span> iCut)<\/span>const<\/span>
\n{<\/span>
\nif<\/span> (<\/span>m_vNodeToRegion[<\/span>src]<\/span> !=<\/span> m_vNodeToRegion[<\/span>dest]<\/span>)<\/span>
\n{<\/span>
\nreturn<\/span> false<\/span>;<\/span>\/\/\u4e0d\u5728\u4e00\u4e2a\u8fde\u901a\u533a\u57df<\/span>
\n}<\/span>
\nif<\/span> (<\/span>!<\/span>m_vCut[<\/span>iCut]<\/span>)<\/span>
\n{<\/span>
\nreturn<\/span> true<\/span>;<\/span>
\n}<\/span>
\nconst<\/span> int<\/span> r1 =<\/span> GetCutRegion<\/span>(<\/span>iCut,<\/span> src)<\/span>;<\/span>
\nconst<\/span> int<\/span> r2 =<\/span> GetCutRegion<\/span>(<\/span>iCut,<\/span> dest)<\/span>;<\/span>
\nreturn<\/span> r1 ==<\/span> r2;<\/span>
\n}<\/span>
\nvector<<\/span>vector<<\/span>int<\/span>>><\/span> GetSubRegionOfCut<\/span>(<\/span>const<\/span> int<\/span> iCut)<\/span>const<\/span>
\n{<\/span>\/\/\u5220\u9664iCut\u53ca\u548c\u5b83\u76f8\u8fde\u7684\u8fb9\u540e，iCut\u6240\u5728\u7684\u533a\u57df\u4f1a\u5206\u6210\u51e0\u4e2a\u533a\u57df：\u7236\u8282\u70b9\u4e00\u4e2a\u533a\u57df\u3001\u5404\u5b50\u8282\u70b9\u4e00\u4e2a\u533a\u57df<\/span>
\n \/\/\u7236\u8282\u70b9\u6240\u5728\u533a\u57df\u53ef\u80fd\u4e3a\u7a7a，\u5982\u679ciCut\u6240\u5728\u7684\u8fde\u901a\u533a\u57df\u53ea\u6709\u4e00\u4e2a\u8282\u70b9，\u5219\u8fd4\u56de\u4e00\u4e2a\u6ca1\u6709\u8282\u70b9\u7684\u533a\u57df\u3002<\/span>
\nconst<\/span> auto<\/span>&<\/span> v =<\/span> m_vChildFirstEnd[<\/span>iCut]<\/span>;<\/span>
\nvector<<\/span>vector<<\/span>int<\/span>>><\/span> vRet<\/span>(<\/span>1<\/span>)<\/span>;<\/span>
\nint<\/span> j =<\/span> 0<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> iTime=<\/span>0<\/span>;<\/span>iTime <<\/span> m_iSize;<\/span> iTime++<\/span> )<\/span>
\n{<\/span>
\nconst<\/span> int<\/span> iNode=<\/span> m_vTimeToNode[<\/span>iTime]<\/span>;<\/span>
\nif<\/span> (<\/span>(<\/span>j <<\/span> v.<\/span>size<\/span>(<\/span>)<\/span>)<\/span> &&<\/span> (<\/span> iTime >=<\/span> v[<\/span>j]<\/span>.<\/span>first )<\/span>)<\/span>
\n{<\/span>
\nj++<\/span>;<\/span>
\nvRet.<\/span>emplace_back<\/span>(<\/span>)<\/span>;<\/span>
\n}<\/span>
\nif<\/span> (<\/span>(<\/span>iCut !=<\/span> iNode)<\/span> &&<\/span> (<\/span>m_vNodeToRegion[<\/span>iNode]<\/span> ==<\/span> m_vNodeToRegion[<\/span>iCut]<\/span>)<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>v.<\/span>size<\/span>(<\/span>)<\/span>&&<\/span>(<\/span>iTime >=<\/span> v.<\/span>back<\/span>(<\/span>)<\/span>.<\/span>second)<\/span>)<\/span>
\n{<\/span>
\nvRet[<\/span>0<\/span>]<\/span>.<\/span>emplace_back<\/span>(<\/span>iNode)<\/span>;<\/span>
\n}<\/span>
\nelse<\/span>
\n{<\/span>
\nvRet.<\/span>back<\/span>(<\/span>)<\/span>.<\/span>emplace_back<\/span>(<\/span>iNode)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> vRet;<\/span>
\n}<\/span>
\nprotected<\/span>:<\/span>
\nint<\/span> dfs<\/span>(<\/span>int<\/span> cur,<\/span> int<\/span> parent,<\/span> const<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> vNeiB)<\/span>
\n{<\/span>
\nauto<\/span>&<\/span> curTime =<\/span> m_vNodeToTime[<\/span>cur]<\/span>;<\/span>
\nm_vNodeToRegion[<\/span>cur]<\/span> =<\/span> m_iRegionCount;<\/span>
\ncurTime =<\/span> m_iTime++<\/span>;<\/span>
\nint<\/span> iCutChild =<\/span> 0<\/span>;<\/span>
\nint<\/span> iMinTime =<\/span> curTime;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> next :<\/span> vNeiB[<\/span>cur]<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>–<\/span>1<\/span> !=<\/span> m_vNodeToTime[<\/span>next]<\/span>)<\/span>
\n{<\/span>
\niMinTime =<\/span> min<\/span>(<\/span>iMinTime,<\/span> m_vNodeToTime[<\/span>next]<\/span>)<\/span>;<\/span>
\ncontinue<\/span>;<\/span>
\n}<\/span>
\nint<\/span> iChildBeginTime =<\/span> m_iTime;<\/span>
\nconst<\/span> int<\/span> iChildMinTime =<\/span> dfs<\/span>(<\/span>next,<\/span> cur,<\/span> vNeiB)<\/span>;<\/span>
\niMinTime =<\/span> min<\/span>(<\/span>iMinTime,<\/span> iChildMinTime)<\/span>;<\/span>
\nif<\/span> (<\/span>iChildMinTime >=<\/span> curTime)<\/span>
\n{<\/span>
\niCutChild++<\/span>;<\/span>
\nm_vChildFirstEnd[<\/span>cur]<\/span>.<\/span>push_back<\/span>(<\/span>{<\/span> iChildBeginTime,<\/span>m_iTime }<\/span>)<\/span>;<\/span>
\n}<\/span>;<\/span>
\n}<\/span>
\nm_vCut[<\/span>cur]<\/span> =<\/span> (<\/span>iCutChild +<\/span> (<\/span>–<\/span>1<\/span> !=<\/span> parent)<\/span>)<\/span> >=<\/span> 2<\/span>;<\/span>
\nreturn<\/span> iMinTime;<\/span>
\n}<\/span>
\nint<\/span> GetCutRegion<\/span>(<\/span>int<\/span> iCut,<\/span> int<\/span> iNode)<\/span>const<\/span>
\n{<\/span>
\nconst<\/span> auto<\/span>&<\/span> v =<\/span> m_vChildFirstEnd[<\/span>iCut]<\/span>;<\/span>
\nauto<\/span> it =<\/span> std::<\/span>upper_bound<\/span>(<\/span>v.<\/span>begin<\/span>(<\/span>)<\/span>,<\/span> v.<\/span>end<\/span>(<\/span>)<\/span>,<\/span> m_vNodeToTime[<\/span>iNode]<\/span>,<\/span> [<\/span>]<\/span>(<\/span>int<\/span> time,<\/span> const<\/span> std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>><\/span>&<\/span> pr)<\/span> {<\/span>return<\/span> time <<\/span> pr.<\/span>first;<\/span> }<\/span>)<\/span>;<\/span>
\nif<\/span> (<\/span>v.<\/span>begin<\/span>(<\/span>)<\/span> ==<\/span> it)<\/span>
\n{<\/span>
\nreturn<\/span> v.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\n}<\/span>
\n—<\/span>it;<\/span>
\nreturn<\/span> (<\/span>it-><\/span>second ><\/span> m_vNodeToTime[<\/span>iNode]<\/span>)<\/span> ?<\/span> (<\/span>it –<\/span> v.<\/span>begin<\/span>(<\/span>)<\/span>)<\/span> :<\/span> v.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\n}<\/span>
\nint<\/span> m_iTime =<\/span> 0<\/span>;<\/span>
\nconst<\/span> int<\/span> m_iSize;<\/span>\/\/\u65f6\u95f4\u6233<\/span>
\nint<\/span> m_iRegionCount =<\/span> 0<\/span>;<\/span>
\nvector<<\/span>int<\/span>><\/span> m_vNodeToTime;<\/span>\/\/\u5404\u8282\u70b9\u5230\u8fbe\u65f6\u95f4，\u4ece0\u5f00\u59cb\u3002 -1\u8868\u793a\u672a\u5904\u7406<\/span>
\nvector<<\/span>bool<\/span>><\/span> m_vCut;<\/span>\/\/\u662f\u5426\u662f\u5272\u70b9<\/span>
\nvector<<\/span>int<\/span>><\/span> m_vNodeToRegion;<\/span>\/\/\u5404\u8282\u70b9\u6240\u5728\u533a\u57df<\/span>
\nvector<<\/span>vector<<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span> m_vChildFirstEnd;<\/span>\/\/\u5de6\u95ed\u53f3\u5f00\u7a7a\u95f4[0,m_vChildFirstEnd[0].first)\u548c[m_vChildFirstEnd.back().second,iSize)\u662f\u4e00\u4e2a\u533a\u57df<\/span>
\nvector<<\/span>int<\/span>><\/span> m_vTimeToNode;<\/span>
\n}<\/span>;<\/span><\/p>\n

2024\u5e743\u67089\u53f7 \u65b0\u5c01\u88c5<\/h2>\n

class<\/span> CNeiBo<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nstatic<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span> Two<\/span>(<\/span>int<\/span> n,<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> edges,<\/span> bool<\/span> bDirect,<\/span> int<\/span> iBase =<\/span> 0<\/span>)<\/span>
\n{<\/span>
\nvector<<\/span>vector<<\/span>int<\/span>>><\/span> vNeiBo<\/span>(<\/span>n)<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> v :<\/span> edges)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase)<\/span>;<\/span>
\nif<\/span> (<\/span>!<\/span>bDirect)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> vNeiBo;<\/span>
\n}<\/span>
\nstatic<\/span> vector<<\/span>vector<<\/span>std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span> Three<\/span>(<\/span>int<\/span> n,<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> edges,<\/span> bool<\/span> bDirect,<\/span> int<\/span> iBase =<\/span> 0<\/span>)<\/span>
\n{<\/span>
\nvector<<\/span>vector<<\/span>std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span> vNeiBo<\/span>(<\/span>n)<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> v :<\/span> edges)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase,<\/span> v[<\/span>2<\/span>]<\/span>)<\/span>;<\/span>
\nif<\/span> (<\/span>!<\/span>bDirect)<\/span>
\n{<\/span>
\nvNeiBo[<\/span>v[<\/span>1<\/span>]<\/span> –<\/span> iBase]<\/span>.<\/span>emplace_back<\/span>(<\/span>v[<\/span>0<\/span>]<\/span> –<\/span> iBase,<\/span> v[<\/span>2<\/span>]<\/span>)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> vNeiBo;<\/span>
\n}<\/span>
\n}<\/span>;<\/span>
\nclass<\/span> CUnionFind<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nCUnionFind<\/span>(<\/span>int<\/span> iSize)<\/span> :<\/span>m_vNodeToRegion<\/span>(<\/span>iSize)<\/span>
\n{<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> iSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nm_vNodeToRegion[<\/span>i]<\/span> =<\/span> i;<\/span>
\n}<\/span>
\nm_iConnetRegionCount =<\/span> iSize;<\/span>
\n}<\/span>
\nCUnionFind<\/span>(<\/span>vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> vNeiBo)<\/span>:<\/span>CUnionFind<\/span>(<\/span>vNeiBo.<\/span>size<\/span>(<\/span>)<\/span>)<\/span>
\n{<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> vNeiBo.<\/span>size<\/span>(<\/span>)<\/span>;<\/span> i++<\/span>)<\/span> {<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> n :<\/span> vNeiBo[<\/span>i]<\/span>)<\/span> {<\/span>
\nUnion<\/span>(<\/span>i,<\/span> n)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\n}<\/span>
\nint<\/span> GetConnectRegionIndex<\/span>(<\/span>int<\/span> iNode)<\/span>
\n{<\/span>
\nint<\/span>&<\/span> iConnectNO =<\/span> m_vNodeToRegion[<\/span>iNode]<\/span>;<\/span>
\nif<\/span> (<\/span>iNode ==<\/span> iConnectNO)<\/span>
\n{<\/span>
\nreturn<\/span> iNode;<\/span>
\n}<\/span>
\nreturn<\/span> iConnectNO =<\/span> GetConnectRegionIndex<\/span>(<\/span>iConnectNO)<\/span>;<\/span>
\n}<\/span>
\nvoid<\/span> Union<\/span>(<\/span>int<\/span> iNode1,<\/span> int<\/span> iNode2)<\/span>
\n{<\/span>
\nconst<\/span> int<\/span> iConnectNO1 =<\/span> GetConnectRegionIndex<\/span>(<\/span>iNode1)<\/span>;<\/span>
\nconst<\/span> int<\/span> iConnectNO2 =<\/span> GetConnectRegionIndex<\/span>(<\/span>iNode2)<\/span>;<\/span>
\nif<\/span> (<\/span>iConnectNO1 ==<\/span> iConnectNO2)<\/span>
\n{<\/span>
\nreturn<\/span>;<\/span>
\n}<\/span>
\nm_iConnetRegionCount—<\/span>;<\/span>
\nif<\/span> (<\/span>iConnectNO1 ><\/span> iConnectNO2)<\/span>
\n{<\/span>
\nUnionConnect<\/span>(<\/span>iConnectNO1,<\/span> iConnectNO2)<\/span>;<\/span>
\n}<\/span>
\nelse<\/span>
\n{<\/span>
\nUnionConnect<\/span>(<\/span>iConnectNO2,<\/span> iConnectNO1)<\/span>;<\/span>
\n}<\/span>
\n}<\/span><\/p>\n

bool<\/span> IsConnect<\/span>(<\/span>int<\/span> iNode1,<\/span> int<\/span> iNode2)<\/span>
\n{<\/span>
\nreturn<\/span> GetConnectRegionIndex<\/span>(<\/span>iNode1)<\/span> ==<\/span> GetConnectRegionIndex<\/span>(<\/span>iNode2)<\/span>;<\/span>
\n}<\/span>
\nint<\/span> GetConnetRegionCount<\/span>(<\/span>)<\/span>const<\/span>
\n{<\/span>
\nreturn<\/span> m_iConnetRegionCount;<\/span>
\n}<\/span>
\nvector<<\/span>int<\/span>><\/span> GetNodeCountOfRegion<\/span>(<\/span>)<\/span>\/\/\u5404\u8054\u901a\u533a\u57df\u7684\u8282\u70b9\u6570\u91cf<\/span>
\n{<\/span>
\nconst<\/span> int<\/span> iNodeSize =<\/span> m_vNodeToRegion.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\nvector<<\/span>int<\/span>><\/span> vRet<\/span>(<\/span>iNodeSize)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> iNodeSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nvRet[<\/span>GetConnectRegionIndex<\/span>(<\/span>i)<\/span>]<\/span>++<\/span>;<\/span>
\n}<\/span>
\nreturn<\/span> vRet;<\/span>
\n}<\/span>
\nstd::<\/span>unordered_map<<\/span>int<\/span>,<\/span> vector<<\/span>int<\/span>>><\/span> GetNodeOfRegion<\/span>(<\/span>)<\/span>
\n{<\/span>
\nstd::<\/span>unordered_map<<\/span>int<\/span>,<\/span> vector<<\/span>int<\/span>>><\/span> ret;<\/span>
\nconst<\/span> int<\/span> iNodeSize =<\/span> m_vNodeToRegion.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> iNodeSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nret[<\/span>GetConnectRegionIndex<\/span>(<\/span>i)<\/span>]<\/span>.<\/span>emplace_back<\/span>(<\/span>i)<\/span>;<\/span>
\n}<\/span>
\nreturn<\/span> ret;<\/span>
\n}<\/span>
\nprivate<\/span>:<\/span>
\nvoid<\/span> UnionConnect<\/span>(<\/span>int<\/span> iFrom,<\/span> int<\/span> iTo)<\/span>
\n{<\/span>
\nm_vNodeToRegion[<\/span>iFrom]<\/span> =<\/span> iTo;<\/span>
\n}<\/span>
\nvector<<\/span>int<\/span>><\/span> m_vNodeToRegion;<\/span>\/\/\u5404\u70b9\u6240\u5728\u8054\u901a\u533a\u57df\u7684\u7d22\u5f15,\u672c\u8054\u901a\u533a\u57df\u4efb\u610f\u4e00\u70b9\u7684\u7d22\u5f15，\u4e3a\u4e86\u589e\u52a0\u53ef\u7406\u89e3\u6027，\u7528\u6700\u5c0f\u7d22\u5f15<\/span>
\nint<\/span> m_iConnetRegionCount;<\/span>
\n}<\/span>;<\/span><\/p>\n

class<\/span> CParents<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nCParents<\/span>(<\/span>vector<<\/span>int<\/span>><\/span>&<\/span> vParent,<\/span> const<\/span> int<\/span> iMaxLeve)<\/span>
\n{<\/span>
\nint<\/span> iBitNum =<\/span> 0<\/span>;<\/span>
\nfor<\/span> (<\/span>;<\/span> (<\/span>1<\/span> <<<\/span> iBitNum)<\/span> <<\/span> iMaxLeve;<\/span> iBitNum++<\/span>)<\/span>;<\/span>
\nconst<\/span> int<\/span> n =<\/span> vParent.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\nm_vParents.<\/span>assign<\/span>(<\/span>iBitNum+<\/span>1<\/span>,<\/span> vector<\/span><<\/span>int<\/span>><\/span><\/span><\/span>(<\/span>n,<\/span> –<\/span>1<\/span>)<\/span>)<\/span>;<\/span>
\nm_vParents[<\/span>0<\/span>]<\/span> =<\/span> vParent;<\/span>
\n\/\/\u6811\u4e0a\u500d\u589e<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 1<\/span>;<\/span> i <<\/span> m_vParents.<\/span>size<\/span>(<\/span>)<\/span>;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nfor<\/span> (<\/span>int<\/span> j =<\/span> 0<\/span>;<\/span> j <<\/span> n;<\/span> j++<\/span>)<\/span>
\n{<\/span>
\nconst<\/span> int<\/span> iPre =<\/span> m_vParents[<\/span>i –<\/span> 1<\/span>]<\/span>[<\/span>j]<\/span>;<\/span>
\nif<\/span> (<\/span>–<\/span>1<\/span> !=<\/span> iPre)<\/span>
\n{<\/span>
\nm_vParents[<\/span>i]<\/span>[<\/span>j]<\/span> =<\/span> m_vParents[<\/span>i –<\/span> 1<\/span>]<\/span>[<\/span>iPre]<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\n}<\/span>
\n}<\/span>
\nint<\/span> GetParent<\/span>(<\/span>int<\/span> iNode,<\/span> int<\/span> iLeve)<\/span>const<\/span>
\n{<\/span>
\nint<\/span> iParent =<\/span> iNode;<\/span>
\nfor<\/span> (<\/span>int<\/span> iBit =<\/span> 0<\/span>;<\/span> iBit <<\/span> m_vParents.<\/span>size<\/span>(<\/span>)<\/span>;<\/span> iBit++<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>–<\/span>1<\/span> ==<\/span> iParent)<\/span>
\n{<\/span>
\nreturn<\/span> iParent;<\/span>
\n}<\/span>
\nif<\/span> (<\/span>iLeve &<\/span> (<\/span>1<\/span> <<<\/span> iBit)<\/span>)<\/span>
\n{<\/span>
\niParent =<\/span> m_vParents[<\/span>iBit]<\/span>[<\/span>iParent]<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> iParent;<\/span>
\n}<\/span>
\nprotected<\/span>:<\/span>
\nvector<<\/span>vector<<\/span>int<\/span>>><\/span> m_vParents;<\/span>
\n}<\/span>;<\/span><\/p>\n

class<\/span> C2Parents<\/span> :<\/span> CParents<\/span><\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nC2Parents<\/span>(<\/span>vector<<\/span>int<\/span>><\/span>&<\/span> vParent,<\/span> const<\/span> vector<<\/span>int<\/span>><\/span>&<\/span> vLeve)<\/span> :<\/span>m_vLeve<\/span>(<\/span>vLeve)<\/span>
\n,<\/span> CParents<\/span>(<\/span>vParent,<\/span>*<\/span>std::<\/span>max_element<\/span>(<\/span>vLeve.<\/span>begin<\/span>(<\/span>)<\/span>,<\/span> vLeve.<\/span>end<\/span>(<\/span>)<\/span>)<\/span>)<\/span>
\n{<\/span>
\n}<\/span>
\nint<\/span> GetPublicParent<\/span>(<\/span>int<\/span> iNode1,<\/span> int<\/span> iNode2)<\/span>const<\/span>
\n{<\/span>
\nint<\/span> leve0 =<\/span> m_vLeve[<\/span>iNode1]<\/span>;<\/span>
\nint<\/span> leve1 =<\/span> m_vLeve[<\/span>iNode2]<\/span>;<\/span>
\nif<\/span> (<\/span>leve0 <<\/span> leve1)<\/span>
\n{<\/span>
\niNode2 =<\/span> GetParent<\/span>(<\/span>iNode2,<\/span> leve1 –<\/span> leve0)<\/span>;<\/span>
\nleve1 =<\/span> leve0;<\/span>
\n}<\/span>
\nelse<\/span>
\n{<\/span>
\niNode1 =<\/span> GetParent<\/span>(<\/span>iNode1,<\/span> leve0 –<\/span> leve1)<\/span>;<\/span>
\nleve0 =<\/span> leve1;<\/span>
\n}<\/span>
\n\/\/\u4e8c\u5206\u67e5\u627e<\/span>
\nint<\/span> left =<\/span> –<\/span>1<\/span>,<\/span> r =<\/span> leve0;<\/span>
\nwhile<\/span> (<\/span>r –<\/span> left ><\/span> 1<\/span>)<\/span>
\n{<\/span>
\nconst<\/span> auto<\/span> mid =<\/span> left +<\/span> (<\/span>r –<\/span> left)<\/span> \/<\/span> 2<\/span>;<\/span>
\nconst<\/span> int<\/span> iParent0 =<\/span> GetParent<\/span>(<\/span>iNode1,<\/span> mid)<\/span>;<\/span>
\nconst<\/span> int<\/span> iParent1 =<\/span> GetParent<\/span>(<\/span>iNode2,<\/span> mid)<\/span>;<\/span>
\nif<\/span> (<\/span>iParent0 ==<\/span> iParent1)<\/span>
\n{<\/span>
\nr =<\/span> mid;<\/span>
\n}<\/span>
\nelse<\/span>
\n{<\/span>
\nleft =<\/span> mid;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> GetParent<\/span>(<\/span>iNode1,<\/span> r)<\/span>;<\/span>
\n}<\/span>
\nprotected<\/span>:<\/span><\/p>\n

vector<<\/span>vector<<\/span>int<\/span>>><\/span> m_vParents;<\/span>
\nconst<\/span> vector<<\/span>int<\/span>><\/span> m_vLeve;<\/span>
\n}<\/span>;<\/span><\/p>\n

\/\/\u5272\u70b9<\/span>
\nclass<\/span> CCutPoint<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nCCutPoint<\/span>(<\/span>const<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> vNeiB)<\/span> :<\/span> m_iSize<\/span>(<\/span>vNeiB.<\/span>size<\/span>(<\/span>)<\/span>)<\/span>
\n{<\/span>
\nm_vNodeToTime.<\/span>assign<\/span>(<\/span>m_iSize,<\/span> –<\/span>1<\/span>)<\/span>;<\/span>
\nm_vCutNewRegion.<\/span>resize<\/span>(<\/span>m_iSize)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> m_iSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>–<\/span>1<\/span> ==<\/span> m_vNodeToTime[<\/span>i]<\/span>)<\/span>
\n{<\/span>
\nm_vRegionFirstTime.<\/span>emplace_back<\/span>(<\/span>m_iTime)<\/span>;<\/span>
\ndfs<\/span>(<\/span>vNeiB,<\/span> i,<\/span> –<\/span>1<\/span>)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\n}<\/span>
\nint<\/span> dfs<\/span>(<\/span>const<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> vNeiB,<\/span>const<\/span> int<\/span> cur,<\/span> const<\/span> int<\/span> parent)<\/span>
\n{<\/span>
\nint<\/span> iMinTime =<\/span> m_vNodeToTime[<\/span>cur]<\/span> =<\/span> m_iTime++<\/span>;<\/span>
\nint<\/span> iRegionCount =<\/span> (<\/span>–<\/span>1<\/span> !=<\/span> parent)<\/span>;<\/span>\/\/\u6839\u8fde\u901a\u533a\u57df\u6570\u91cf<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> next :<\/span> vNeiB[<\/span>cur]<\/span>)<\/span>{<\/span>
\nif<\/span> (<\/span>–<\/span>1<\/span> !=<\/span> m_vNodeToTime[<\/span>next]<\/span>)<\/span>{<\/span>
\niMinTime =<\/span> min<\/span>(<\/span>iMinTime,<\/span> m_vNodeToTime[<\/span>next]<\/span>)<\/span>;<\/span>
\ncontinue<\/span>;<\/span>
\n}<\/span>
\nconst<\/span> int<\/span> childMinTime =<\/span> dfs<\/span>(<\/span>vNeiB,<\/span> next,<\/span> cur)<\/span>;<\/span>
\niMinTime =<\/span> min<\/span>(<\/span>iMinTime,<\/span> childMinTime)<\/span>;<\/span>
\nif<\/span> (<\/span>childMinTime >=<\/span> m_vNodeToTime[<\/span>cur]<\/span>)<\/span>{<\/span>
\niRegionCount++<\/span>;<\/span>
\nm_vCutNewRegion[<\/span>cur]<\/span>.<\/span>emplace_back<\/span>(<\/span>m_vNodeToTime[<\/span>next]<\/span>,<\/span> m_iTime)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nif<\/span> (<\/span>iRegionCount <<\/span> 2<\/span>)<\/span>
\n{<\/span>
\nm_vCutNewRegion[<\/span>cur]<\/span>.<\/span>clear<\/span>(<\/span>)<\/span>;<\/span>
\n}<\/span>
\nreturn<\/span> iMinTime;<\/span>
\n}<\/span>
\nconst<\/span> int<\/span> m_iSize;<\/span>
\nconst<\/span> vector<<\/span>int<\/span>><\/span>&<\/span> Time<\/span>(<\/span>)<\/span>const<\/span> {<\/span> return<\/span> m_vNodeToTime;<\/span> }<\/span>\/\/\u5404\u8282\u70b9\u7684\u65f6\u95f4\u6233<\/span>
\nconst<\/span> vector<<\/span>int<\/span>><\/span>&<\/span> RegionFirstTime<\/span>(<\/span>)<\/span>const<\/span> {<\/span> return<\/span> m_vRegionFirstTime;<\/span> }<\/span>\/\/\u5404\u8fde\u901a\u533a\u57df\u7684\u6700\u5c0f\u65f6\u95f4\u6233<\/span>
\nvector<<\/span>bool<\/span>><\/span> Cut<\/span>(<\/span>)<\/span>const<\/span> {<\/span>
\nvector<<\/span>bool<\/span>><\/span> ret;<\/span>
\nfor<\/span> (<\/span>int<\/span> i =<\/span> 0<\/span>;<\/span> i <<\/span> m_iSize;<\/span> i++<\/span>)<\/span>
\n{<\/span>
\nret.<\/span>emplace_back<\/span>(<\/span>m_vCutNewRegion[<\/span>i]<\/span>.<\/span>size<\/span>(<\/span>)<\/span>)<\/span>;<\/span>
\n}<\/span>
\nreturn<\/span> ret;<\/span> }<\/span>\/\/<\/span>
\nconst<\/span> vector <<\/span> vector<<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span>&<\/span> NewRegion<\/span>(<\/span>)<\/span>const<\/span> {<\/span> return<\/span> m_vCutNewRegion;<\/span> }<\/span>;<\/span>
\nprotected<\/span>:<\/span>
\nvector<<\/span>int<\/span>><\/span> m_vNodeToTime;<\/span>
\nvector<<\/span>int<\/span>><\/span> m_vRegionFirstTime;<\/span>
\nvector <<\/span> vector<<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span> m_vCutNewRegion;<\/span> \/\/m_vCutNewRegion[c]\u5982\u679c\u5b58\u5728[left,r) \u8868\u793a\u5272\u6389c\u540e，\u65f6\u95f4\u6233[left,r)\u7684\u8282\u70b9\u4f1a\u5f62\u6210\u65b0\u533a\u57df<\/span>
\nint<\/span> m_iTime =<\/span> 0<\/span>;<\/span>
\n}<\/span>;<\/span><\/p>\n

class<\/span> CConnectAfterCutPoint<\/span>
\n{<\/span>
\npublic<\/span>:<\/span>
\nCConnectAfterCutPoint<\/span>(<\/span>const<\/span> vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> vNeiB)<\/span> :<\/span>m_ct<\/span>(<\/span>vNeiB)<\/span>
\n{<\/span>
\nm_vTimeToNode.<\/span>resize<\/span>(<\/span>m_ct.<\/span>m_iSize)<\/span>;<\/span>
\nm_vNodeToRegion.<\/span>resize<\/span>(<\/span>m_ct.<\/span>m_iSize)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> iNode =<\/span> 0<\/span>;<\/span> iNode <<\/span> m_ct.<\/span>m_iSize;<\/span> iNode++<\/span>)<\/span>
\n{<\/span>
\nm_vTimeToNode[<\/span>m_ct.<\/span>Time<\/span>(<\/span>)<\/span>[<\/span>iNode]<\/span>]<\/span> =<\/span> iNode;<\/span>
\n}<\/span>
\nfor<\/span> (<\/span>int<\/span> iTime =<\/span> 0<\/span>,<\/span>iRegion=<\/span> 0<\/span>;<\/span> iTime <<\/span> m_ct.<\/span>m_iSize;<\/span> iTime++<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>(<\/span>iRegion <<\/span> m_ct.<\/span>RegionFirstTime<\/span>(<\/span>)<\/span>.<\/span>size<\/span>(<\/span>)<\/span>)<\/span> &&<\/span> (<\/span>m_ct.<\/span>RegionFirstTime<\/span>(<\/span>)<\/span>[<\/span>iRegion]<\/span> ==<\/span> iTime)<\/span>)<\/span>
\n{<\/span>
\niRegion++<\/span>;<\/span>
\n}<\/span>
\nm_vNodeToRegion[<\/span>m_vTimeToNode[<\/span>iTime]<\/span>]<\/span> =<\/span> (<\/span>iRegion –<\/span> 1<\/span>)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nbool<\/span> Connect<\/span>(<\/span>int<\/span> src,<\/span> int<\/span> dest,<\/span> int<\/span> iCut)<\/span>const<\/span>
\n{<\/span>
\nif<\/span> (<\/span>m_vNodeToRegion[<\/span>src]<\/span> !=<\/span> m_vNodeToRegion[<\/span>dest]<\/span>)<\/span>
\n{<\/span>
\nreturn<\/span> false<\/span>;<\/span>\/\/\u4e0d\u5728\u4e00\u4e2a\u8fde\u901a\u533a\u57df<\/span>
\n}<\/span>
\nif<\/span> (<\/span>0<\/span> ==<\/span> m_ct.<\/span>NewRegion<\/span>(<\/span>)<\/span>[<\/span>iCut]<\/span>.<\/span>size<\/span>(<\/span>)<\/span>)<\/span>
\n{<\/span>\/\/\u4e0d\u662f\u5272\u70b9<\/span>
\nreturn<\/span> true<\/span>;<\/span>
\n}<\/span>
\nconst<\/span> int<\/span> r1 =<\/span> GetCutRegion<\/span>(<\/span>iCut,<\/span> src)<\/span>;<\/span>
\nconst<\/span> int<\/span> r2 =<\/span> GetCutRegion<\/span>(<\/span>iCut,<\/span> dest)<\/span>;<\/span>
\nreturn<\/span> r1 ==<\/span> r2;<\/span>
\n}<\/span>
\nvector<<\/span>vector<<\/span>int<\/span>>><\/span> GetSubRegionOfCut<\/span>(<\/span>const<\/span> int<\/span> iCut)<\/span>const<\/span>
\n{<\/span>\/\/\u5220\u9664iCut\u53ca\u548c\u5b83\u76f8\u8fde\u7684\u8fb9\u540e，iCut\u6240\u5728\u7684\u533a\u57df\u4f1a\u5206\u6210\u51e0\u4e2a\u533a\u57df：\u7236\u8282\u70b9\u4e00\u4e2a\u533a\u57df\u3001\u5404\u5b50\u8282\u70b9\u4e00\u4e2a\u533a\u57df<\/span>
\n\/\/\u7236\u8282\u70b9\u6240\u5728\u533a\u57df\u53ef\u80fd\u4e3a\u7a7a，\u5982\u679ciCut\u6240\u5728\u7684\u8fde\u901a\u533a\u57df\u53ea\u6709\u4e00\u4e2a\u8282\u70b9，\u5219\u8fd4\u56de\u4e00\u4e2a\u6ca1\u6709\u8282\u70b9\u7684\u533a\u57df\u3002<\/span>
\nconst<\/span> auto<\/span>&<\/span> v =<\/span> m_ct.<\/span>NewRegion<\/span>(<\/span>)<\/span>[<\/span>iCut]<\/span>;<\/span>
\nvector<<\/span>int<\/span>><\/span> vParen;<\/span>
\nconst<\/span> int<\/span> iRegion =<\/span> m_vNodeToRegion[<\/span>iCut]<\/span>;<\/span>
\nconst<\/span> int<\/span> iEndTime =<\/span> (<\/span>iRegion +<\/span> 1<\/span> ==<\/span> m_ct.<\/span>RegionFirstTime<\/span>(<\/span>)<\/span>.<\/span>size<\/span>(<\/span>)<\/span>)<\/span> ?<\/span> m_ct.<\/span>m_iSize :<\/span> m_ct.<\/span>RegionFirstTime<\/span>(<\/span>)<\/span>[<\/span>iRegion+<\/span>1<\/span>]<\/span>;<\/span>
\nvector<<\/span>vector<<\/span>int<\/span>>><\/span> vRet;<\/span>
\nfor<\/span> (<\/span>int<\/span> iTime =<\/span> m_ct.<\/span>RegionFirstTime<\/span>(<\/span>)<\/span>[<\/span>iRegion]<\/span>,<\/span>j=<\/span>–<\/span>1<\/span>;<\/span> iTime <<\/span> iEndTime;<\/span> iTime++<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>iCut ==<\/span> m_vTimeToNode[<\/span>iTime]<\/span>)<\/span>
\n{<\/span>
\ncontinue<\/span>;<\/span>
\n}<\/span>
\nif<\/span> (<\/span>(<\/span>j +<\/span> 1<\/span> <<\/span> v.<\/span>size<\/span>(<\/span>)<\/span>)<\/span> &&<\/span> (<\/span>v[<\/span>j +<\/span> 1<\/span>]<\/span>.<\/span>first ==<\/span> iTime)<\/span>)<\/span>
\n{<\/span>
\nj++<\/span>;<\/span>
\nvRet.<\/span>emplace_back<\/span>(<\/span>)<\/span>;<\/span>
\n}<\/span>
\nconst<\/span> int<\/span> iNode =<\/span> m_vTimeToNode[<\/span>iTime]<\/span>;<\/span>
\nif<\/span> (<\/span>(<\/span>–<\/span>1<\/span> !=<\/span> j )<\/span> &&<\/span> (<\/span>iTime >=<\/span> v[<\/span>j]<\/span>.<\/span>first)<\/span> &&<\/span> (<\/span>iTime <<\/span> v[<\/span>j]<\/span>.<\/span>second)<\/span>)<\/span>
\n{<\/span>
\nvRet.<\/span>back<\/span>(<\/span>)<\/span>.<\/span>emplace_back<\/span>(<\/span>iNode)<\/span>;<\/span>
\n}<\/span>
\nelse<\/span>
\n{<\/span>
\nvParen.<\/span>emplace_back<\/span>(<\/span>iNode)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nvRet.<\/span>emplace_back<\/span>(<\/span>)<\/span>;<\/span>
\nvRet.<\/span>back<\/span>(<\/span>)<\/span>.<\/span>swap<\/span>(<\/span>vParen)<\/span>;<\/span>
\nreturn<\/span> vRet;<\/span>
\n}<\/span>
\nprotected<\/span>:<\/span>
\nint<\/span> GetCutRegion<\/span>(<\/span>int<\/span> iCut,<\/span> int<\/span> iNode)<\/span>const<\/span>
\n{<\/span>
\nconst<\/span> auto<\/span>&<\/span> v =<\/span> m_ct.<\/span>NewRegion<\/span>(<\/span>)<\/span>[<\/span>iCut]<\/span>;<\/span>
\nauto<\/span> it =<\/span> std::<\/span>upper_bound<\/span>(<\/span>v.<\/span>begin<\/span>(<\/span>)<\/span>,<\/span> v.<\/span>end<\/span>(<\/span>)<\/span>,<\/span> m_ct.<\/span>Time<\/span>(<\/span>)<\/span>[<\/span>iNode]<\/span>,<\/span> [<\/span>]<\/span>(<\/span>int<\/span> time,<\/span> const<\/span> std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>><\/span>&<\/span> pr)<\/span> {<\/span>return<\/span> time <<\/span> pr.<\/span>first;<\/span> }<\/span>)<\/span>;<\/span>
\nif<\/span> (<\/span>v.<\/span>begin<\/span>(<\/span>)<\/span> ==<\/span> it)<\/span>
\n{<\/span>
\nreturn<\/span> v.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\n}<\/span>
\n—<\/span>it;<\/span>
\nreturn<\/span> (<\/span>it-><\/span>second ><\/span> m_ct.<\/span>Time<\/span>(<\/span>)<\/span>[<\/span>iNode]<\/span>)<\/span> ?<\/span> (<\/span>it –<\/span> v.<\/span>begin<\/span>(<\/span>)<\/span>)<\/span> :<\/span> v.<\/span>size<\/span>(<\/span>)<\/span>;<\/span>
\n}<\/span>
\nvector<<\/span>int<\/span>><\/span> m_vTimeToNode;<\/span>
\nvector<<\/span>int<\/span>><\/span> m_vNodeToRegion;<\/span>\/\/\u5404\u8282\u70b9\u6240\u5728\u533a\u57df<\/span>
\nconst<\/span> CCutPoint m_ct;<\/span>
\n}<\/span>;<\/span><\/p>\n

class<\/span> Solution<\/span> {<\/span>
\npublic<\/span>:<\/span>
\nvector<<\/span>int<\/span>><\/span> countPairsOfConnectableServers<\/span>(<\/span>vector<<\/span>vector<<\/span>int<\/span>>><\/span>&<\/span> edges,<\/span> int<\/span> signalSpeed)<\/span> {<\/span>
\nm_c =<\/span> edges.<\/span>size<\/span>(<\/span>)<\/span> +<\/span> 1<\/span>;<\/span>
\nm_vDisToRoot.<\/span>resize<\/span>(<\/span>m_c)<\/span>;<\/span>
\nm_vParent.<\/span>resize<\/span>(<\/span>m_c)<\/span>;<\/span>
\nm_vLeve.<\/span>resize<\/span>(<\/span>m_c)<\/span>;<\/span>
\nauto<\/span> neiBo =<\/span> CNeiBo<\/span>::<\/span>Three<\/span>(<\/span>m_c,<\/span> edges,<\/span> false<\/span>,<\/span> 0<\/span>)<\/span>;<\/span>
\nDFS<\/span>(<\/span>neiBo,<\/span> 0<\/span>,<\/span> –<\/span>1<\/span>,<\/span> 0<\/span>,<\/span> 0<\/span>)<\/span>;<\/span>
\nC2Parents par<\/span>(<\/span>m_vParent,<\/span> m_vLeve)<\/span>;<\/span>
\nauto<\/span> neiBo2 =<\/span> CNeiBo<\/span>::<\/span>Two<\/span>(<\/span>m_c,<\/span> edges,<\/span> false<\/span>,<\/span> 0<\/span>)<\/span>;<\/span>
\nCConnectAfterCutPoint cut<\/span>(<\/span>neiBo2)<\/span>;<\/span>
\nvector<<\/span>int<\/span>><\/span> vRet<\/span>(<\/span>m_c)<\/span>;<\/span>
\nfor<\/span> (<\/span>int<\/span> c =<\/span> 0<\/span>;<\/span> c <<\/span> m_c;<\/span> c++<\/span>)<\/span>
\n{<\/span>
\nauto<\/span> regs =<\/span> cut.<\/span>GetSubRegionOfCut<\/span>(<\/span>c)<\/span>;<\/span>
\nint<\/span> left =<\/span> 0<\/span>;<\/span>
\nint<\/span>&<\/span> iRet =<\/span> vRet[<\/span>c]<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> subRegion :<\/span> regs)<\/span>
\n{<\/span>
\nint<\/span> cur =<\/span> 0<\/span>;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> ab :<\/span> subRegion)<\/span>
\n{<\/span>
\nconst<\/span> int<\/span> pub =<\/span> par.<\/span>GetPublicParent<\/span>(<\/span>ab,<\/span> c)<\/span>;<\/span>
\nconst<\/span> int<\/span> len =<\/span> m_vDisToRoot[<\/span>ab]<\/span> +<\/span> m_vDisToRoot[<\/span>c]<\/span> –<\/span> 2<\/span> *<\/span> m_vDisToRoot[<\/span>pub]<\/span>;<\/span>
\nif<\/span> (<\/span>0<\/span> !=<\/span> len %<\/span> signalSpeed)<\/span>
\n{<\/span>
\ncontinue<\/span>;<\/span>
\n}<\/span>
\ncur++<\/span>;<\/span>
\n}<\/span>
\niRet +=<\/span> left *<\/span> cur;<\/span>
\nleft +=<\/span> cur;<\/span>
\n}<\/span>
\n}<\/span>
\nreturn<\/span> vRet;<\/span>
\n}<\/span>
\nvoid<\/span> DFS<\/span>(<\/span>vector<<\/span>vector<<\/span>std::<\/span>pair<<\/span>int<\/span>,<\/span> int<\/span>>><\/span>><\/span>&<\/span> neiBo,<\/span> int<\/span> cur,<\/span> int<\/span> par,<\/span> int<\/span> leve,<\/span> int<\/span> dis)<\/span>
\n{<\/span>
\nm_vDisToRoot[<\/span>cur]<\/span> =<\/span> dis;<\/span>
\nm_vParent[<\/span>cur]<\/span> =<\/span> par;<\/span>
\nm_vLeve[<\/span>cur]<\/span> =<\/span> leve;<\/span>
\nfor<\/span> (<\/span>const<\/span> auto<\/span>&<\/span> [<\/span>next,<\/span> len]<\/span> :<\/span> neiBo[<\/span>cur]<\/span>)<\/span>
\n{<\/span>
\nif<\/span> (<\/span>next ==<\/span> par)<\/span>
\n{<\/span>
\ncontinue<\/span>;<\/span>
\n}<\/span>
\nDFS<\/span>(<\/span>neiBo,<\/span> next,<\/span> cur,<\/span> leve +<\/span> 1<\/span>,<\/span> dis +<\/span> len)<\/span>;<\/span>
\n}<\/span>
\n}<\/span>
\nvector<<\/span>int<\/span>><\/span> m_vDisToRoot,<\/span> m_vParent,<\/span> m_vLeve;<\/span>
\nint<\/span> m_c;<\/span>
\n}<\/span>;<\/span><\/p>\n

DFS\u4ee3\u66ff\u6811\u4e0a\u500d\u589e<\/h2>\n

\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u74f6\u9888\u5728 \u6811\u4e0a\u500d\u589e\u3002\u53ef\u4ee5\u76f4\u63a5DFS \u6700\u8fd1\u516c\u5171\u7956\u5148\u3002<\/p>\n

\"\"<\/p>\n

\u6269\u5c55\u9605\u8bfb<\/h2>\n

\u89c6\u9891\u8bfe\u7a0b<\/h4>\n

\u6709\u6548\u5b66\u4e60：\u660e\u786e\u7684\u76ee\u6807 \u53ca\u65f6\u7684\u53cd\u9988 \u62c9\u4f38\u533a（\u96be\u5ea6\u5408\u9002），\u53ef\u4ee5\u5148\u5b66\u7b80\u5355\u7684\u8bfe\u7a0b，\u8bf7\u79fb\u6b65CSDN\u5b66\u9662，\u542c\u767d\u94f6\u8bb2\u5e08（\u4e5f\u5c31\u662f\u9119\u4eba）\u7684\u8bb2\u89e3\u3002 https:\/\/edu.csdn.net\/course\/detail\/38771<\/p>\n

\u5982\u4f55\u4f60\u60f3\u5feb\u901f\u5f62\u6210\u6218\u6597\u4e86，\u4e3a\u8001\u677f\u5206\u5fe7，\u8bf7\u5b66\u4e60C#\u5165\u804c\u57f9\u8bad\u3001C++\u5165\u804c\u57f9\u8bad\u7b49\u8bfe\u7a0b https:\/\/edu.csdn.net\/lecturer\/6176<\/p>\n

\u76f8\u5173<\/h4>\n

\u4e0b\u8f7d<\/p>\n

\u60f3\u9ad8\u5c4b\u5efa\u74f4\u7684\u5b66\u4e60\u7b97\u6cd5，\u8bf7\u4e0b\u8f7d\u300a\u559c\u7f3a\u5168\u4e66\u7b97\u6cd5\u518c\u300bdoc\u7248 https:\/\/download.csdn.net\/download\/he_zhidan\/88348653<\/p>\n\n\u6211\u60f3\u5bf9\u5927\u5bb6\u8bf4\u7684\u8bdd<\/tr>\n\n\n\n\n
\u95fb\u7f3a\u9677\u5219\u559c\u662f\u4e00\u4e2a\u7f8e\u597d\u7684\u613f\u671b，\u65e9\u53d1\u73b0\u95ee\u9898，\u65e9\u4fee\u6539\u95ee\u9898，\u7ed9\u8001\u677f\u8282\u7ea6\u94b1\u3002<\/td>\n<\/tr>\n
\u5b50\u58a8\u5b50\u8a00\u4e4b：\u4e8b\u65e0\u7ec8\u59cb，\u65e0\u52a1\u591a\u4e1a\u3002\u4e5f\u5c31\u662f\u6211\u4eec\u5e38\u8bf4\u7684\u4e13\u4e1a\u7684\u4eba\u505a\u4e13\u4e1a\u7684\u4e8b\u3002<\/td>\n<\/tr>\n
\u5982\u679c\u7a0b\u5e8f\u662f\u4e00\u6761\u9f99，\u90a3\u7b97\u6cd5\u5c31\u662f\u4ed6\u7684\u662f\u775b<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\u6d4b\u8bd5\u73af\u5883<\/h4>\n

\u64cd\u4f5c\u7cfb\u7edf：win7 \u5f00\u53d1\u73af\u5883： VS2019 C++17 \u6216\u8005 \u64cd\u4f5c\u7cfb\u7edf：win10 \u5f00\u53d1\u73af\u5883： VS2022 **C+<\/p>\n

+17** \u5982\u65e0\u7279\u6b8a\u8bf4\u660e，\u672c\u7b97\u6cd5\u7528**C++**\u5b9e\u73b0\u3002<\/p>\n

\"\"<\/p>\n","protected":false},"excerpt":{"rendered":"

\u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb4.8k\u6b21\uff0c\u70b9\u8d5e93\u6b21\uff0c\u6536\u85cf87\u6b21\u3002\u672c\u6587\u56f4\u7ed5LeetCode3067\u9898\uff0c\u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee\u5c55\u5f00\u3002\u6d89\u53ca\u6811\u4e0a\u500d\u589e\u3001\u5e76\u96c6\u67e5\u627e\u3001\u6362\u6839\u6cd5DFS\u7b49\u77e5\u8bc6\u70b9\uff0c\u4ecb\u7ecd\u4e86\u8ba1\u7b97\u6811\u4e0a\u8282\u70b9\u8ddd\u79bb\u3001\u627e\u6700\u65e9\u516c\u5171\u7956\u5148\u3001\u5224\u65ad\u8def\u5f84\u516c\u5171\u8fb9\u7684\u65b9\u6cd5\uff0c\u8fd8\u63d0\u53ca\u7528DFS\u4ee3\u66ff\u6811\u4e0a\u500d\u589e\u4ee5\u4f18\u5316\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u7b97\u6cd5\u7528C++\u5b9e\u73b0\u3002<\/p>\n","protected":false},"author":2,"featured_media":25263,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[1981,55,1984,1985,1986,1982,1987,1983],"topic":[],"class_list":["post-25267","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-server","tag-1981","tag-c","tag-1984","tag-1985","tag-1986","tag-1982","tag-1987","tag-1983"],"yoast_head":"\n\u3010\u6811\u4e0a\u500d\u589e\u3011\u3010\u5272\u70b9\u3011 \u3010\u6362\u6839\u6cd5\u30113067. \u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.wsisp.com\/helps\/25267.html\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u3010\u6811\u4e0a\u500d\u589e\u3011\u3010\u5272\u70b9\u3011 \u3010\u6362\u6839\u6cd5\u30113067. \u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"og:description\" content=\"\u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb4.8k\u6b21\uff0c\u70b9\u8d5e93\u6b21\uff0c\u6536\u85cf87\u6b21\u3002\u672c\u6587\u56f4\u7ed5LeetCode3067\u9898\uff0c\u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee\u5c55\u5f00\u3002\u6d89\u53ca\u6811\u4e0a\u500d\u589e\u3001\u5e76\u96c6\u67e5\u627e\u3001\u6362\u6839\u6cd5DFS\u7b49\u77e5\u8bc6\u70b9\uff0c\u4ecb\u7ecd\u4e86\u8ba1\u7b97\u6811\u4e0a\u8282\u70b9\u8ddd\u79bb\u3001\u627e\u6700\u65e9\u516c\u5171\u7956\u5148\u3001\u5224\u65ad\u8def\u5f84\u516c\u5171\u8fb9\u7684\u65b9\u6cd5\uff0c\u8fd8\u63d0\u53ca\u7528DFS\u4ee3\u66ff\u6811\u4e0a\u500d\u589e\u4ee5\u4f18\u5316\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u7b97\u6cd5\u7528C++\u5b9e\u73b0\u3002\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.wsisp.com\/helps\/25267.html\" \/>\n<meta property=\"og:site_name\" content=\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"article:published_time\" content=\"2025-04-19T04:06:19+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2025\/04\/20250419040617-68032139a2cf5.png\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"20 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/25267.html\",\"url\":\"https:\/\/www.wsisp.com\/helps\/25267.html\",\"name\":\"\u3010\u6811\u4e0a\u500d\u589e\u3011\u3010\u5272\u70b9\u3011 \u3010\u6362\u6839\u6cd5\u30113067. \u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"isPartOf\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\"},\"datePublished\":\"2025-04-19T04:06:19+00:00\",\"dateModified\":\"2025-04-19T04:06:19+00:00\",\"author\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/25267.html#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.wsisp.com\/helps\/25267.html\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/25267.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/www.wsisp.com\/helps\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u3010\u6811\u4e0a\u500d\u589e\u3011\u3010\u5272\u70b9\u3011 \u3010\u6362\u6839\u6cd5\u30113067. \u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\",\"url\":\"https:\/\/www.wsisp.com\/helps\/\",\"name\":\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"description\":\"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"contentUrl\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"caption\":\"admin\"},\"sameAs\":[\"http:\/\/wp.wsisp.com\"],\"url\":\"https:\/\/www.wsisp.com\/helps\/author\/admin\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u3010\u6811\u4e0a\u500d\u589e\u3011\u3010\u5272\u70b9\u3011 \u3010\u6362\u6839\u6cd5\u30113067. \u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.wsisp.com\/helps\/25267.html","og_locale":"zh_CN","og_type":"article","og_title":"\u3010\u6811\u4e0a\u500d\u589e\u3011\u3010\u5272\u70b9\u3011 \u3010\u6362\u6839\u6cd5\u30113067. \u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","og_description":"\u6587\u7ae0\u6d4f\u89c8\u9605\u8bfb4.8k\u6b21\uff0c\u70b9\u8d5e93\u6b21\uff0c\u6536\u85cf87\u6b21\u3002\u672c\u6587\u56f4\u7ed5LeetCode3067\u9898\uff0c\u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee\u5c55\u5f00\u3002\u6d89\u53ca\u6811\u4e0a\u500d\u589e\u3001\u5e76\u96c6\u67e5\u627e\u3001\u6362\u6839\u6cd5DFS\u7b49\u77e5\u8bc6\u70b9\uff0c\u4ecb\u7ecd\u4e86\u8ba1\u7b97\u6811\u4e0a\u8282\u70b9\u8ddd\u79bb\u3001\u627e\u6700\u65e9\u516c\u5171\u7956\u5148\u3001\u5224\u65ad\u8def\u5f84\u516c\u5171\u8fb9\u7684\u65b9\u6cd5\uff0c\u8fd8\u63d0\u53ca\u7528DFS\u4ee3\u66ff\u6811\u4e0a\u500d\u589e\u4ee5\u4f18\u5316\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u7b97\u6cd5\u7528C++\u5b9e\u73b0\u3002","og_url":"https:\/\/www.wsisp.com\/helps\/25267.html","og_site_name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","article_published_time":"2025-04-19T04:06:19+00:00","og_image":[{"url":"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2025\/04\/20250419040617-68032139a2cf5.png"}],"author":"admin","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"admin","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"20 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.wsisp.com\/helps\/25267.html","url":"https:\/\/www.wsisp.com\/helps\/25267.html","name":"\u3010\u6811\u4e0a\u500d\u589e\u3011\u3010\u5272\u70b9\u3011 \u3010\u6362\u6839\u6cd5\u30113067. \u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","isPartOf":{"@id":"https:\/\/www.wsisp.com\/helps\/#website"},"datePublished":"2025-04-19T04:06:19+00:00","dateModified":"2025-04-19T04:06:19+00:00","author":{"@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41"},"breadcrumb":{"@id":"https:\/\/www.wsisp.com\/helps\/25267.html#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.wsisp.com\/helps\/25267.html"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.wsisp.com\/helps\/25267.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/www.wsisp.com\/helps"},{"@type":"ListItem","position":2,"name":"\u3010\u6811\u4e0a\u500d\u589e\u3011\u3010\u5272\u70b9\u3011 \u3010\u6362\u6839\u6cd5\u30113067. \u5728\u5e26\u6743\u6811\u7f51\u7edc\u4e2d\u7edf\u8ba1\u53ef\u8fde\u63a5\u670d\u52a1\u5668\u5bf9\u6570\u76ee"}]},{"@type":"WebSite","@id":"https:\/\/www.wsisp.com\/helps\/#website","url":"https:\/\/www.wsisp.com\/helps\/","name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","description":"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41","name":"admin","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/","url":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","contentUrl":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","caption":"admin"},"sameAs":["http:\/\/wp.wsisp.com"],"url":"https:\/\/www.wsisp.com\/helps\/author\/admin"}]}},"_links":{"self":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/25267","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/comments?post=25267"}],"version-history":[{"count":0,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/25267\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media\/25263"}],"wp:attachment":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media?parent=25267"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/categories?post=25267"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/tags?post=25267"},{"taxonomy":"topic","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/topic?post=25267"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}