{"id":111,"date":"2023-03-30T21:58:29","date_gmt":"2023-03-30T13:58:29","guid":{"rendered":"https:\/\/solost.cn\/?p=111"},"modified":"2023-03-30T21:58:29","modified_gmt":"2023-03-30T13:58:29","slug":"211","status":"publish","type":"post","link":"https:\/\/solost.cn\/?p=111","title":{"rendered":"AcWing – 3696. \u6784\u9020\u6709\u5411\u65e0\u73af\u56fe"},"content":{"rendered":"

\"image.png\"<\/p>\n

\u9898\u76ee\u94fe\u63a5<\/h2>\n

\u9898\u76ee\u94fe\u63a5<\/a><\/p>\n

\u9898\u76ee\u5927\u610f<\/h2>\n

\u8fd9\u9053\u9898\u5c31\u662f\u7ed9\u4f60\u4e00\u5806\u8fb9\uff0c\u6709\u4e9b\u8fb9\u662f\u786e\u5b9a\u65b9\u5411\u7684\uff0c\u6709\u4e9b\u8fb9\u662f\u4e0d\u786e\u5b9a\u65b9\u5411\u7684\uff0c\u95ee\u4f60\u5c06\u8fd9\u4e9b\u4e0d\u786e\u5b9a\u65b9\u5411\u7684\u8fb9\u600e\u4e48\u653e\u6ee1\u8db3\u8fd9\u4e2a\u56fe\u662f\u4e00\u4e2a\u6709\u5411\u65e0\u73af\u56fe<\/p>\n

\u9898\u89e3<\/h2>\n

\u8fd9\u9053\u9898\u95ee\u662f\u4e0d\u662f\u6709\u5411\u65e0\u73af\u56fe\uff0c\u90a3\u4e48\u5c31\u662f\u95ee\u662f\u4e0d\u662f\u62d3\u6251\u56fe\uff0c\u6240\u4ee5\u8981\u8fdb\u884c\u62d3\u6251\u6392\u5e8f\uff0c\u5982\u679c\u5df2\u6709\u7684\u8fb9\u5df2\u7ecf\u4e0d\u662f\u62d3\u6251\u56fe\uff0c\u90a3\u4e48\u600e\u4e48\u52a0\u8fb9\u4e5f\u4e0d\u662f\u62d3\u6251\u56fe\uff0c\u6240\u4ee5\u5148\u5224\u65ad\u7ed9\u7684\u786e\u5b9a\u7684\u8fb9\u662f\u4e0d\u662f\u62d3\u6251\u56fe\uff0c\u5982\u679c\u662f\u62d3\u6251\u56fe\uff0c\u90a3\u4e48\u80af\u5b9a\u4f1a\u7b97\u51fa\u6765\u4e00\u4e2a\u62d3\u6251\u5e8f\uff0c\u7136\u540e\u628a\u90a3\u4e9b\u4e0d\u786e\u5b9a\u7684\u8fb9\u6309\u7167\u62d3\u6251\u5e8f\u6392\u5217\u5373\u53ef\u3002\u8fd9\u4e2a\u9b3c\u9898\u522b\u5fd8\u4e86\u5c06\u6240\u6709\u7684\u5168\u5c40\u53d8\u91cf\u90fd\u521d\u59cb\u5316\uff0c\u8981\u4e0d\u7136\u51fa\u73b0\u4e00\u5806\u4ec0\u4e48\u9b3c\uff0cpos\u6807\u8bb0\u7684\u65f6\u5019\u521a\u5f00\u59cb\u7528\u7684\u662fvector\u5f00\u4e86n\u7684\u5927\u5c0f\uff0c\u6211\u5c31\u4e0d\u77e5\u9053\u4e3a\u5565\u4f1a\u62a5\u9519\uff0c\u6362\u6210map\u5c31\u8fc7\u4e86\u3002<\/p>\n

#include <algorithm>\n#include <bitset>\n#include <cmath>\n#include <cstdio>\n#include <cstdlib>\n#include <cstring>\n#include <fstream>\n#include <iostream>\n#include <map>\n#include <queue>\n#include <set>\n#include <stack>\n#include <unordered_map>\n#include <unordered_set>\n#include <vector>\n\nusing namespace std;\n#define x first\n#define y second\n#define endl '\\n'\n#define IOS                       \\\n    ios_base::sync_with_stdio(0); \\\n    cin.tie(0);                   \\\n    cout.tie(0);\ntypedef long long ll;\ntypedef pair<int, int> PII;\ntypedef unsigned long long ull;\nconst int INF = 0x3f3f3f3f, mod = 1000000007;\nconst int N = 2e5 + 10;\nint n, m;\nint d[N];\nvector<int> ans;\nvector<PII> v;\nvector<int> a[N];\nbool topsort()\n{\n    queue<int> q;\n    for (int i = 1; i <= n; i++) {\n        if (!d[i])\n            q.push(i);\n    }\n    while (q.size()) {\n        auto t = q.front();\n        ans.push_back(t);\n        q.pop();\n        for (auto x : a[t]) {\n            if (--d[x] == 0) {\n                q.push(x);\n            }\n        }\n    }\n    return ans.size() == n;\n}\n\nvoid solve()\n{\n    memset(d, 0, sizeof d);\n    ans.clear();\n    v.clear();\n    cin >> n >> m;\n    for (int i = 1; i <= n; i++) {\n        a[i].clear();\n    }\n    while (m--) {\n        int op, x, y;\n        cin >> op >> x >> y;\n        if (op) {\n            a[x].push_back(y);\n            d[y]++;\n        } else {\n            v.push_back({ x, y });\n        }\n    }\n    if (!topsort())\n        cout << "NO\\n";\n    else {\n        cout << "YES\\n";\n        unordered_map<int, int> pos;\n        for (int i = 0; i < ans.size(); i++) {\n            pos[ans[i]] = i;\n        }\n        for (int i = 1; i <= n; i++) {\n            for (auto x : a[i]) {\n                cout << i << " " << x << endl;\n            }\n        }\n        for (auto [x, y] : v) {\n            if (pos[x] > pos[y])\n                cout << y << " " << x << endl;\n            else\n                cout << x << " " << y << endl;\n        }\n    }\n}\nint main()\n{\n    IOS;\n    int t = 1;\n    cin >> t;\n    while (t--) {\n        solve();\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u94fe\u63a5 \u9898\u76ee\u94fe\u63a5 \u9898\u76ee\u5927\u610f \u8fd9\u9053\u9898\u5c31\u662f\u7ed9\u4f60\u4e00\u5806\u8fb9\uff0c\u6709\u4e9b\u8fb9\u662f\u786e\u5b9a\u65b9\u5411\u7684\uff0c\u6709\u4e9b\u8fb9\u662f\u4e0d\u786e\u5b9a\u65b9\u5411\u7684\uff0c\u95ee\u4f60\u5c06\u8fd9\u4e9b\u4e0d\u786e\u5b9a\u65b9\u5411\u7684\u8fb9\u600e\u4e48\u653e\u6ee1\u8db3\u8fd9\u4e2a\u56fe\u662f\u4e00\u4e2a\u6709\u5411\u65e0\u73af\u56fe \u9898\u89e3 \u8fd9\u9053\u9898\u95ee\u662f\u4e0d\u662f\u6709\u5411\u65e0\u73af\u56fe\uff0c\u90a3\u4e48\u5c31\u662f\u95ee\u662f\u4e0d\u662f\u62d3\u6251\u56fe\uff0c\u6240\u4ee5\u8981\u8fdb\u884c\u62d3\u6251\u6392\u5e8f\uff0c\u5982\u679c\u5df2\u6709\u7684\u8fb9\u5df2\u7ecf\u4e0d\u662f\u62d3\u6251\u56fe\uff0c\u90a3\u4e48\u600e\u4e48\u52a0\u8fb9\u4e5f\u4e0d\u662f\u62d3\u6251\u56fe\uff0c\u6240\u4ee5\u5148\u5224\u65ad\u7ed9\u7684\u786e\u5b9a\u7684\u8fb9\u662f\u4e0d\u662f\u62d3\u6251\u56fe\uff0c\u5982\u679c\u662f\u62d3\u6251\u56fe\uff0c\u90a3\u4e48\u80af\u5b9a\u4f1a\u7b97\u51fa\u6765\u4e00\u4e2a\u62d3\u6251\u5e8f\uff0c\u7136\u540e\u628a\u90a3\u4e9b\u4e0d\u786e\u5b9a\u7684\u8fb9\u6309\u7167\u62d3\u6251\u5e8f\u6392\u5217\u5373\u53ef\u3002\u8fd9\u4e2a\u9b3c\u9898\u522b\u5fd8\u4e86\u5c06\u6240\u6709\u7684\u5168\u5c40\u53d8\u91cf\u90fd\u521d\u59cb\u5316\uff0c\u8981\u4e0d\u7136\u51fa\u73b0\u4e00\u5806\u4ec0\u4e48\u9b3c\uff0cpos\u6807\u8bb0\u7684\u65f6\u5019\u521a\u5f00\u59cb\u7528\u7684\u662fvector\u5f00\u4e86n\u7684\u5927\u5c0f\uff0c\u6211\u5c31\u4e0d\u77e5\u9053\u4e3a\u5565\u4f1a\u62a5\u9519\uff0c\u6362\u6210map\u5c31\u8fc7\u4e86\u3002 #include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <fstream> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <unordered_map> #include <unordered_set> #include <vector> using namespace std; #define x first #define y second #define endl '\\n' #define IOS \\ ios_base::sync_with_stdio(0); \\ cin.tie(0); \\ […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[45,38],"class_list":["post-111","post","type-post","status-publish","format-standard","hentry","category-solution","tag-45","tag-38"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/111","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=111"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/111\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=111"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=111"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=111"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}