{"id":667,"date":"2023-10-04T19:41:53","date_gmt":"2023-10-04T11:41:53","guid":{"rendered":"http:\/\/ggapa.net:81\/?p=667"},"modified":"2023-11-09T21:08:19","modified_gmt":"2023-11-09T13:08:19","slug":"dfs-%e5%ba%8f%e5%9c%a8%e7%a5%96%e5%85%88%e9%97%ae%e9%a2%98%e7%9a%84%e4%bd%bf%e7%94%a8","status":"publish","type":"post","link":"http:\/\/ggapa.net:81\/2023\/10\/04\/dfs-%e5%ba%8f%e5%9c%a8%e7%a5%96%e5%85%88%e9%97%ae%e9%a2%98%e7%9a%84%e4%bd%bf%e7%94%a8\/","title":{"rendered":"DFS \u5e8f\u5728\u7956\u5148\u95ee\u9898\u7684\u4f7f\u7528"},"content":{"rendered":"

\u7956\u5b59\u8be2\u95ee<\/a><\/p>\n

\u6b64\u95ee\u9898\u53ef\u4ee5\u7528 LCA \u6765\u89e3\u51b3\uff0c\u4f46\u662f LCA \u7684\u7801\u91cf\u5927\uff0c\u800c\u4e14\u53ef\u80fd\u5bb9\u6613\u5199\u6302\uff0c\u5c24\u5176\u662f\u50cf\u6211\u8fd9\u79cd\u849f\u84bb<\/del><\/p>\n

\u5982\u679c\u5361\u65f6\u95f4\u7684\u8bdd\u6709\u53ef\u80fd\u500d\u589e\/\u91cd\u94fe\u5256\u5206 LCA \u90fd\u8981\u6302\u6389\uff0c\u8fd9\u65f6\u5019\u5c31\u662f DFS \u5e8f\u53d1\u6325\u4f5c\u7528\u7684\u65f6\u5019\u4e86\u3002<\/p>\n

\n

\u62ff\u4e00\u4e2a\u8ba1\u6570\u5668\u3002\u5728\u904d\u5386\u5230\u6bcf\u4e00\u4e2a\u8282\u70b9\u7684\u65f6\u5019\uff0c\u6211\u4eec\u5728\u8fdb\u5165\u5b83\u7684\u65f6\u5019\u8bb0\u5f55\u4e00\u4e0b\uff0c\u5728\u79bb\u5f00\u5b83\u7684\u65f6\u5019\u4e5f\u8bb0\u5f55\u4e00\u4e0b\uff0c\u5728\u8bb0\u5f55\u5b8c\u6210\u540e\u5c31\u5f97\u5230\u4e86\u4e00\u4e2a\u6811\u7684 DFS \u5e8f<\/p>\n

\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n

\/*\nLOJ10135\nhttps:\/\/loj.ac\/p\/10135\n*\/\n#include <iostream>\n#include <vector>\nusing namespace std;\nconst int maxn = 4e4 + 5;\n\nint n, m, root;\nvector<int> G[maxn];\nint ti;\nint in[maxn], out[maxn];\n\nvoid dfs(int x) {\n    if(in[x] != 0) return;\n    in[x] = ++ti;\n    for(int to : G[x]) dfs(to);\n    out[x] = ++ti;\n}\n\nint ask(int x, int y) {\n\n    return in[x] < in[y] && in[y] < out[y] && out[y] < out[x];\n}\n\nint main() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    cin >> n;\n    for(int i = 1, u, v; i <= n; i++) {\n        cin >> u >> v;\n        if(v == -1) {\n            root = u;\n            continue;\n        }\n        G[u].push_back(v);\n        G[v].push_back(u);\n    }\n    dfs(root);\n    cin >> m;\n    for(int i = 1, u, v; i <= m; i++) {\n        cin >> u >> v;\n        if(ask(u, v)) cout << 1 << "\\n";\n        else if(ask(v, u)) cout << 2 << "\\n";\n        else cout << 0 << "\\n";\n    }\n    return 0;\n} \n\n\/\/106ms<\/code><\/pre>\n
\u4e0e\u500d\u589e LCA \u76f8\u6bd4\uff0c\u5feb\u4e86\u4e9b\u8bb8<\/p>\n
\u7956\u5b59\u8be2\u95ee(LOJ10135)\nhttps:\/\/vjudge.csgrandeur.cn\/contest\/584212#problem\/D\n*\/\n#include <iostream>\n#include <vector>\nusing namespace std;\nconst int maxn = 4e4 + 5;\nconst int maxk = 20; \n\nint n, root, m;\nvector<int> G[maxn];\n\nint fa[maxk][maxn];\nint depth[maxn];\n\nvoid dfs(int x, int f) {\n    fa[0][x] = f;\n    depth[x] = depth[f] + 1;\n    for (int i = 1; i < maxk; i++) {\n        fa[i][x] = fa[i - 1][fa[i - 1][x]];\n    }\n    for (auto to : G[x]) {\n        if (to == f)\n            continue;\n        dfs(to, x);\n    }\n}\n\nint LCA(int x, int y) {\n    if (depth[x] < depth[y])\n        swap(x, y);\n    for (int i = maxk - 1; i >= 0; i--) {\n        if (depth[fa[i][x]] >= depth[y])\n            x = fa[i][x];\n    }\n    if (x == y)\n        return x;\n    for (int i = maxk - 1; i >= 0; i--) {\n        if (fa[i][x] != fa[i][y]) {\n            x = fa[i][x];\n            y = fa[i][y];\n        }\n    }\n    return fa[0][x];\n}\n\nint main() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    cin >> n;\n    for(int i = 1, u, v; i <= n; i++) {\n        cin >> u >> v;\n        if(v == -1) {root = u; continue;}\n        G[u].push_back(v);\n        G[v].push_back(u);\n    }\n    cin >> m;\n    int x, y;\n    dfs(root, 0);\n    while(m--) {\n        cin >> x >> y;\n        int lca = LCA(x, y);\n        if(lca == x) cout << "1\\n";\n        else if(lca == y) cout << "2\\n";\n        else cout << "0\\n";\n    }\n}\n\/\/130ms<\/code><\/pre>\n
\u56e0\u4e3a\u5728\u4f7f\u7528 DFS \u5e8f\u89e3\u51b3\u95ee\u9898\u65f6\uff0c\u5b83\u7684\u67e5\u8be2\u662f\u5e38\u6570\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u6240\u4ee5\u8bf4\u8981\u5feb\u5f88\u591a\u3002<\/p>\n
\u5f53\u7136\uff0cDFS \u5e8f\u4e5f\u53ef\u4ee5\u7528\u4e8eLCA\u95ee\u9898\u4e2d\uff0c\u8be6\u89c1\u8fd9\u7bc7\u6587\u7ae0<\/a>\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u7956\u5b59\u8be2\u95ee \u6b64\u95ee\u9898\u53ef\u4ee5\u7528 LCA \u6765\u89e3\u51b3\uff0c\u4f46\u662f LCA \u7684\u7801\u91cf\u5927\uff0c\u800c\u4e14\u53ef\u80fd\u5bb9\u6613\u5199\u6302\uff0c\u5c24\u5176\u662f\u50cf\u6211\u8fd9\u79cd\u849f\u84bb \u5982\u679c\u5361\u65f6 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"_links":{"self":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/667"}],"collection":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/comments?post=667"}],"version-history":[{"count":3,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/667\/revisions"}],"predecessor-version":[{"id":839,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/667\/revisions\/839"}],"wp:attachment":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/media?parent=667"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/categories?post=667"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/tags?post=667"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}