\u6b64\u6587\u4ec5\u4e3a\u4f5c\u8005\u590d\u4e60\u6240\u7528\uff0c\u65e0\u6559\u7a0b\u4f5c\u7528\u3002<\/p>\n
\u5728\u56fe\u8bba\u4e2d\uff0c\u62d3\u6251\u6392\u5e8f\uff08Topological Sorting\uff09\u662f\u4e00\u79cd\u9488\u5bf9<\/strong>\u6709\u5411\u65e0\u73af\u56fe<\/span>\uff08DAG, Directed Acyclic Graph\uff09\u7684\u7ebf\u6027\u6392\u5e8f\u7b97\u6cd5\uff0c\u5176\u6838\u5fc3\u4f5c\u7528\u662f\u786e\u5b9a\u56fe\u4e2d\u8282\u70b9\u7684\u4f9d\u8d56\u987a\u5e8f\uff0c\u4f7f\u5f97\u6240\u6709\u8fb9\u7684\u65b9\u5411\u5728\u6392\u5e8f\u4e2d\u4fdd\u6301\u4e00\u81f4\u3002<\/span><\/p>\n \u90bb\u63a5\u8868\u6216\u94fe\u5f0f\u524d\u5411\u661f<\/p>\n\u4f7f\u7528<\/h2>\n
\n
\u5e38\u7528\u7b97\u6cd5 Kahn (\u57fa\u4e8e\u5165\u5ea6\u7684\u7c7bbfs)<\/h2>\n
\n
\u5b58\u56fe\u65b9\u5f0f<\/h2>\n
\n1.\u6700\u5927\u98df\u7269\u94fe\u8ba1\u6570 \u666e\u53ca\/\u63d0\u9ad8-<\/span><\/h1>\n
\u5f00\u80c3\u5c0f\u83dc<\/del><\/p>\n\u9898\u76ee\u63cf\u8ff0<\/h2>\n
\n
\n\u4e00\u884c\u4e00\u4e2a\u6574\u6570\uff0c\u4e3a\u6700\u5927\u98df\u7269\u94fe\u6570\u91cf\u6a21\u4e0a\u00a080112002<\/span><\/span><\/span><\/span>\u00a0\u7684\u7ed3\u679c\u3002<\/li>\n<\/ul>\n\u793a\u4f8b<\/h2>\n
\n
\n5 7
\n1 2
\n1 3
\n2 3
\n3 5
\n2 5
\n4 5
\n3 4<\/li>\n
\n5<\/li>\n<\/ul>\n\u601d\u8def<\/h2>\n
\n
\u4ee3\u7801<\/h2>\n
\u94fe\u5f0f\u524d\u5411\u661f<\/h3>\n
const int N = 1e6 + 10 , mod = 80112002;\r\nint e[N] , ne[N] , h[N] , idx;\r\nint in[N] , out[N];\r\nint n , m;\r\nint value[N];\r\nint ans = 0;\r\n\r\nvoid add(int a , int b)\r\n{\r\n e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;\r\n}\r\n\r\nvoid bfs()\r\n{\r\n queue<int> q;\r\n for (int i = 1 ; i <= n ; i ++ )\r\n if (!in[i]) q.push(i) , value[i] = 1;\r\n \r\n while (q.size())\r\n {\r\n int index = q.front();\r\n q.pop();\r\n\r\n for (int i = h[index] ; ~i ; i = ne[i])\r\n {\r\n int j = e[i];\r\n in[j] --;\r\n\r\n value[j] = (value[j] + value[index]) % mod;\r\n\r\n if (!in[j]) q.push(j);\r\n }\r\n }\r\n\r\n for (int i = 1 ; i <= n ; i ++ )\r\n {\r\n if (!out[i])\r\n ans = (ans + value[i]) % mod; \r\n }\r\n return ;\r\n\r\n}\r\n\r\nvoid solve()\r\n{\r\n memset(h , -1 , sizeof h);\r\n cin >> n >> m;\r\n for (int i = 1 ; i <= m ; i ++ )\r\n {\r\n int a , b;\r\n cin >> a >> b;\r\n add(a , b);\r\n out[a] ++ , in[b] ++;\r\n }\r\n\r\n bfs();\r\n\r\n cout << ans << endl;\r\n}<\/pre>\n\u90bb\u63a5\u8868<\/h3>\n
const int N = 1e6 + 10 , mod = 80112002;\r\nvector<int> g[N];\r\nint in[N] , out[N];\r\nint n , m;\r\nint value[N];\r\nint ans = 0;\r\n\r\nvoid bfs()\r\n{\r\n queue<int> q;\r\n for (int i = 1 ; i <= n ; i ++ )\r\n if (!in[i]) q.push(i) , value[i] = 1;\r\n \r\n while (q.size())\r\n {\r\n int index = q.front();\r\n q.pop();\r\n\r\n int l = g[index].size();\r\n for (int i = 0 ; i < l ; i ++ )\r\n {\r\n int v = g[index][i];\r\n\r\n in[v] --;\r\n value[v] = (value[v] + value[index]) % mod;\r\n\r\n if (!in[v])\r\n q.push(v);\r\n }\r\n }\r\n\r\n for (int i = 1 ; i <= n ; i ++ )\r\n {\r\n if (!out[i]) ans = (ans + value[i]) % mod;\r\n }\r\n}<\/pre>\n2.\u6444\u50cf\u5934 \u666e\u53ca\/\u63d0\u9ad8-<\/span><\/h1>\n
\u9898\u76ee\u63cf\u8ff0<\/h2>\n