首页 > 代码库 > BZOJ1654 [Usaco2006 Jan]The Cow Prom 奶牛舞会
BZOJ1654 [Usaco2006 Jan]The Cow Prom 奶牛舞会
看不懂题，蒟蒻中文英文都太差了。。。
于是Orz itwiiioi巨巨！
结果终于理解了：就是求有向图非单点的强连通分量个数。
tarjan妥妥的。。。（板子*1 get√）
1 /************************************************************** 2 Problem: 1654 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:32 ms 7 Memory:1476 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13 14 using namespace std;15 const int N = 10005;16 const int M = 50005;17 struct edges{18 int next, to;19 }e[M];20 int n, m;21 int cnt, top, num, tot, ans, sz;22 int dfn[N], low[N], vis[N], s[N], first[N];23 24 inline int read(){25 int x = 0, sgn = 1;26 char ch = getchar();27 while (ch < ‘0‘ || ch > ‘9‘){28 if (ch == ‘-‘) sgn = -1;29 ch = getchar();30 }31 while (ch >= ‘0‘ && ch <= ‘9‘){32 x = x * 10 + ch - ‘0‘;33 ch = getchar();34 }35 return sgn * x;36 }37 38 inline void add_edge(int x, int y){39 e[++tot].next = first[x];40 first[x] = tot;41 e[tot].to = y;42 }43 44 void DFS(int p){45 dfn[p] = low[p] = ++cnt;46 s[++top] = p, vis[p] = 1;47 int x, y;48 for (x = first[p]; x; x = e[x].next){49 y = e[x].to;50 if (!vis[y]) DFS(y);51 if (vis[y] < 2)52 low[p] = min(low[p], low[y]);53 }54 if (dfn[p] == low[p]){55 ++num, sz = 0;56 while (s[top + 1] != p){57 y = s[top--];58 vis[y] = 2;59 ++sz;60 }61 if (sz != 1) ++ ans;62 }63 }64 65 inline void tarjan(){66 cnt = top = num = 0;67 memset(vis, sizeof(vis), 0);68 for (int i = 1; i <= n; ++i)69 if (!vis[i]) DFS(i);70 }71 72 int main(){73 n = read(), m = read();74 int x, y;75 for (int i = 1; i <= m; ++i){76 x = read(), y = read();77 add_edge(x, y);78 }79 tarjan();80 printf("%d\n", ans);81 return 0;82 }
（p.s. 为什么改进版比不改进版要慢。。。这不科学的T T）
BZOJ1654 [Usaco2006 Jan]The Cow Prom 奶牛舞会
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。