开始: 2024-11-25 00:00:00

(24-25赛季)稠州常规赛12

结束: 2024-11-28 00:00:00
当前  2025-01-24 13:00:40  类型: IOI  状态: 已经结束 

P4. 找环
描述

给定n个点和m组关系,请你找出其中有几个环,环的意思是,通过这些连边可以走回到出发的起点,我们称之为回环!

输入

两个数字n个点和m条边

接下来m行,每行两个数字uv,表示uv有一条单向边


输出

有一个数字k表示有k个环

样例

输入

5 5
1 2
2 1
3 4
4 5
5 3

输出

2

输入

6 6
1 2
3 4
2 3
4 1
6 5
6 5

输出

1
提示

样例说明:

1->2->1,3->4->5->3,所有有两个环!

40%的数据,n,m\leq 30

100%的数据,n,m\leq 10^5,1\leq u,v\leq n

数据保证,要么是链要么是环,没有环上分支的情况!

提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交