The Cow Prom
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 1137 | Accepted: 716 |
Description
The N (2 <= N <= 10,000) cows are so excited: it's prom night! They are dressed in their finest gowns, complete with corsages and new shoes. They know that tonight they will each try to perform the Round Dance.
Only cows can perform the Round Dance which requires a set of ropes and a circular stock tank. To begin, the cows line up around a circular stock tank and number themselves in clockwise order consecutively from 1..N. Each cow faces the tank so she can see the other dancers.
They then acquire a total of M (2 <= M <= 50,000) ropes all of which are distributed to the cows who hold them in their hooves. Each cow hopes to be given one or more ropes to hold in both her left and right hooves; some cows might be disappointed.
For the Round Dance to succeed for any given cow (say, Bessie), the ropes that she holds must be configured just right. To know if Bessie's dance is successful, one must examine the set of cows holding the other ends of her ropes (if she has any), along with the cows holding the other ends of any ropes they hold, etc. When Bessie dances clockwise around the tank, she must instantly pull all the other cows in her group around clockwise, too. Likewise,
if she dances the other way, she must instantly pull the entire group counterclockwise (anti-clockwise in British English).
Of course, if the ropes are not properly distributed then a set of cows might not form a proper dance group and thus can not succeed at the Round Dance. One way this happens is when only one rope connects two cows. One cow could pull the other in one direction, but could not pull the other direction (since pushing ropes is well-known to be fruitless). Note that the cows must Dance in lock-step: a dangling cow (perhaps with just one rope) that is eventually pulled along disqualifies a group from properly performing the Round Dance since she is not immediately pulled into lockstep with the rest.
Given the ropes and their distribution to cows, how many groups of cows can properly perform the Round Dance? Note that a set of ropes and cows might wrap many times around the stock tank.
Only cows can perform the Round Dance which requires a set of ropes and a circular stock tank. To begin, the cows line up around a circular stock tank and number themselves in clockwise order consecutively from 1..N. Each cow faces the tank so she can see the other dancers.
They then acquire a total of M (2 <= M <= 50,000) ropes all of which are distributed to the cows who hold them in their hooves. Each cow hopes to be given one or more ropes to hold in both her left and right hooves; some cows might be disappointed.
For the Round Dance to succeed for any given cow (say, Bessie), the ropes that she holds must be configured just right. To know if Bessie's dance is successful, one must examine the set of cows holding the other ends of her ropes (if she has any), along with the cows holding the other ends of any ropes they hold, etc. When Bessie dances clockwise around the tank, she must instantly pull all the other cows in her group around clockwise, too. Likewise,
if she dances the other way, she must instantly pull the entire group counterclockwise (anti-clockwise in British English).
Of course, if the ropes are not properly distributed then a set of cows might not form a proper dance group and thus can not succeed at the Round Dance. One way this happens is when only one rope connects two cows. One cow could pull the other in one direction, but could not pull the other direction (since pushing ropes is well-known to be fruitless). Note that the cows must Dance in lock-step: a dangling cow (perhaps with just one rope) that is eventually pulled along disqualifies a group from properly performing the Round Dance since she is not immediately pulled into lockstep with the rest.
Given the ropes and their distribution to cows, how many groups of cows can properly perform the Round Dance? Note that a set of ropes and cows might wrap many times around the stock tank.
Input
Line 1: Two space-separated integers: N and M
Lines 2..M+1: Each line contains two space-separated integers A and B that describe a rope from cow A to cow B in the clockwise direction.
Lines 2..M+1: Each line contains two space-separated integers A and B that describe a rope from cow A to cow B in the clockwise direction.
Output
Line 1: A single line with a single integer that is the number of groups successfully dancing the Round Dance.
Sample Input
5 4 2 4 3 5 1 2 4 1
Sample Output
1
Hint
Explanation of the sample:
ASCII art for Round Dancing is challenging. Nevertheless, here is a representation of the cows around the stock tank:
ASCII art for Round Dancing is challenging. Nevertheless, here is a representation of the cows around the stock tank:
_1___ /**** \ 5 /****** 2 / /**TANK**| \ \********/ \ \******/ 3 \ 4____/ / \_______/Cows 1, 2, and 4 are properly connected and form a complete Round Dance group. Cows 3 and 5 don't have the second rope they'd need to be able to pull both ways, thus they can not properly perform the Round Dance.
题意:
求出强连通分量中的点集大于等于2的点的强连通分量个数。
思路:
强连通分量。增加一数组记录点集个数,后遍历一遍计算即可。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <stack> using namespace std; const int NMAX = 10005; const int EMAX = 50005; int n, m, ind; int fir[NMAX], next[EMAX], v[EMAX]; int cmp[NMAX], low[NMAX], pre[NMAX], num[NMAX]; int scc_cnt, dfs_clock; stack<int> s; void add_edge(int f, int t) { v[ind] = t; next[ind] = fir[f]; fir[f] = ind; ++ind; } void dfs(int u) { pre[u] = low[u] = ++dfs_clock; s.push(u); for (int e = fir[u]; e != -1; e = next[e]) { if (!pre[ v[e] ]) { dfs( v[e] ); low[u] = min(low[u], low[ v[e] ]); } else if (!cmp[ v[e] ]) { low[u] = min(low[u], pre[ v[e] ]); } } if (low[u] == pre[u]) { ++scc_cnt; for (;;) { int x = s.top(); s.pop(); cmp[x] = scc_cnt; ++num[scc_cnt]; if (x == u) break; } } } void scc() { scc_cnt = dfs_clock = 0; memset(cmp, 0, sizeof(cmp)); memset(pre, 0, sizeof(pre)); for (int u = 1; u <= n; ++u) if (!pre[u]) dfs(u); } int main() { ind = 0; memset(fir, -1, sizeof(fir)); memset(num, 0 , sizeof(num)); scanf("%d%d", &n, &m); while (m--) { int f, t; scanf("%d%d", &f, &t); add_edge(f, t); } scc(); int ans = 0; for (int i = 1; i <= scc_cnt; ++i) if (num[i] >= 2) ++ans; printf("%d\n", ans); return 0; }
相关推荐
进行数据挖掘的一个有力的工具,界面图形化,通俗易懂!是荷兰大学著名教授和过程挖掘教授关于过程挖掘的解释和说明.针对日志时间进行的过程挖掘,也叫工作流挖掘的一个基础认识.
ProM是一个可扩展的框架,支持插件形式的各种过程挖掘技术。它是独立于平台的,因为它是用Java实现的。压缩包内包含两个子压缩包: 1.prom-lite-1.1-local.zip:由于服务器在国外,下载插件非常非常慢,这里是官方...
home_prom_graf Prometheus + Grafana堆栈使用来自micro:bit的数据构建,并带有连接的环境传感器(bme280环境,tcs3472颜色和mems麦克风)和外部源去做: []设置Grafana并保存模板[]进行PromQL查询以制作热图或平均...
e2prom通过i2c总线的读写 注释少了点 自己编的
蓝桥杯c语言 蓝桥杯c语言嵌入式练习题之E2PROM+题解
xilinx FPGA PROM 加载设计
Platform Flash PROM User Guide,Platform Flash PROM User Guide,Platform Flash PROM User Guide,Platform Flash PROM User Guide
CAT24WC01/02/04/08/16 是一个1K/2K/4K/8K/16K 位串行CMOS E2PROM 内部含有 128/256/512/1024/2048 个8 位字节CATALYST 公司的先进CMOS 技术实质上减少了器件的功耗 CAT24WC01 有一个8 字节页写缓冲器CAT24WC02/04/...
prom软件自带的示例日志,可进行alpha挖掘,启发式挖掘等挖掘操作
实现E2PROM的读写,包括写E2PROM,读E2PROM
用于在纯C环境下对E2PROM空间进行名字管理,即以数字{1
详细的介绍了xilinx fpga的prom配置流程
Java Prom 2015
ATMEL E2prom 读写时序以及说明
自己编写的e2prom程序,掌握I2C总线的原理,通过自己写程序才知道那里不足!
Xilinx FPGA的PROM配置 作者:枪手
FX-10-20GM-PROM手册pdf,FX-10-20GM-PROM手册
PCIE X4转4路千兆网intel_i350 e2prom+spiflash 4光口4电口配置文件,用于I350网卡硬件开发: i350_at25256_NET.bin i350_at25256_SFP.bin i350_m25p40_NET.bin i350_m25p40_SFP.bin
原创,51单片机读写E2PROM程序. KEIL UV3编译环境.
# Prom6.8/6.9插件包 百度网盘 链接:https://pan.baidu.com/s/12JiE2wtjKHLUOzRv-3u1Jg