原题见COGS
tarjan的典型题、入门题，真的是裸的tarjan。
这道题就是先搜索强连通，再统计强连通的出度，如果有两个或以上出度为零的强连通，则此题无解。
最后输出唯一的强连通的大小，也就是它内部的点的个数。
代码推荐以新页面打开，因为有些注释打的有点长。。//话说这是我第一次写注释把注释打这么详细啊
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
#include <iostream> #include <cstdio> #include <algorithm> const int MX = 10005; using namespace std; int low[MX], dfn[MX], cnt[MX], n, m, be[MX], sccn; bool out[MX]; class stack {//手写栈 private: int s[MX]; int top_; bool instack[MX]; public: int top() { return s[top_]; } void pop() { instack[s[top_]] = false; top_--; } void push(int num) { instack[num] = true; s[++top_] = num; } bool in(int num) { return instack[num]; } }s; struct edge { int to, ne; }e[MX * 5];//邻接表存边 int head[MX], tot; void tarjan(int now) { int to; low[now] = dfn[now] = ++tot;//dfn为当前文件序号, low是一个tarjan独有的特殊数组。。。 s.push(now); for (int i = head[now]; i; i = e[i].ne) { to = e[i].to; if (!dfn[to]) {//如果之前没有访问过该节点 tarjan(to);//循环进行深搜 low[now] = min(low[to], low[now]);//更新low值 } else if (s.in(to)) {//已经访问过该节点，并且是在这次深搜中访问的，表明有环 low[now] = min(low[to], low[now]);//更新low值 } } if (dfn[now] == low[now]) {//进行缩点 int tmp; sccn++;//强连通的编号 do { tmp = s.top(); s.pop(); cnt[sccn]++; be[tmp] = sccn;//tmp属于的强连通 }while (tmp != now); } } void addedge(int x0, int y0) {//邻接表加边 tot++; e[tot].to = y0; e[tot].ne = head[x0]; head[x0] = tot; } int get_num() {//日常读入优化 int ans = 0; char tmp; tmp = getchar(); while (tmp > '9' || tmp < '0') tmp = getchar(); while (tmp <= '9' && tmp >= '0') { ans = ans * 10 + tmp - 48; tmp = getchar(); } return ans; } int Main() { //freopen("cow.in", "r", stdin); //freopen("cow.out", "w", stdout); n = get_num(); m = get_num(); int x, y; for (int i = 1; i <= m; i++) { x = get_num(); y = get_num(); addedge(x, y); } for (int i = 1; i <= n; i++) { if(!dfn[i]) tarjan(i);//如果该节点并没有被访问过，进行深搜遍历 } for (int i = 1; i <= n; i++) { for (int j = head[i]; j; j = e[j].ne) { if (be[i] != be[e[j].to]) {//如果该节点和它指向的节点不属于同一个强连通 out[be[i]] = true;//就说明这个强连通有出度 break;//然后证明这个节点不是我们要找的答案，可以直接遍历下一个节点 } } } int tmp = 0; int ans = 0; for (int i = 1; i <= sccn; i++) { if (!out[i]) {//如果这个节点没有出度 ans = cnt[i];//更新答案 tmp++;//没有出度的强连通的个数 } if (tmp == 2) {//如果有一个以上的没有出度的强连通，则此题无解 cout << "0" << endl; return 0; } } cout << ans << endl; return 0; } int AA = Main();//对于COGS的一点神奇的优化，至今不明原理 int main() {;} |