CF659E.New Reform

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Berland has n cities connected by m bidirectional roads. No road connects a city to itself, and each pair of cities is connected by no more than one road. It is not guaranteed that you can get from any city to any other one, using only the existing roads.

The President of Berland decided to make changes to the road system and instructed the Ministry of Transport to make this reform. Now, each road should be unidirectional (only lead from one city to another).

In order not to cause great resentment among residents, the reform needs to be conducted so that there can be as few separate cities as possible. A city is considered separate, if no road leads into it, while it is allowed to have roads leading from this city.

Help the Ministry of Transport to find the minimum possible number of separate cities after the reform.

伯兰德有 nn 座城市,由 mm 条双向道路连接。不存在连接某座城市到其自身的道路,且任意两座城市之间至多只有一条道路相连。不能保证仅通过现有道路就能从任意一座城市到达另一座城市。

伯兰德总统决定对道路系统进行改革,并指示交通部执行此项改革。改革后,每条道路都必须改为单向(即仅从一座城市通向另一座城市)。

为避免在居民中引发强烈不满,此次改革需尽可能减少“孤立城市”的数量。“孤立城市”定义为:没有任何道路通向该城市的那些城市(但允许从该城市出发的道路存在)。

请帮助交通部求出改革后孤立城市的最小可能数量。

输入格式

The first line of the input contains two positive integers, n and m — the number of the cities and the number of roads in Berland (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000).

Next m lines contain the descriptions of the roads: the i-th road is determined by two distinct integers x__i, y__i (1 ≤ x__i, y__i ≤ n, x__i ≠ y__i), where x__i and y__i are the numbers of the cities connected by the i-th road.

It is guaranteed that there is no more than one road between each pair of cities, but it is not guaranteed that from any city you can get to any other one, using only roads.

输入的第一行包含两个正整数 nn 和 mm —— 分别表示 Berland 的城市数量和道路数量(2 ≤ n ≤ 100 0002 \leq n \leq 100\,000,1 ≤ m ≤ 100 0001 \leq m \leq 100\,000)。

接下来的 mm 行描述了各条道路:第 ii 条道路由两个互异的整数 xi, yix_i,\,y_i(1 ≤ xi, yi ≤ n1 \leq x_i,\,y_i \leq n,且 xi ≠ yix_i \neq y_i)确定,其中 xix_i 和 yiy_i 是该道路所连接的两座城市的编号。

保证任意一对城市之间至多只有一条道路,但不保证从任意一座城市出发仅通过道路均可到达其他任意一座城市。

输出格式

Print a single integer — the minimum number of separated cities after the reform.

输出一个整数——改革后分离城市的最少数量。

输入输出样例

  • 输入#1

    4 3
    2 1
    1 3
    4 3

    输出#1

    1
  • 输入#2

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

    输出#2

    0
  • 输入#3

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

    输出#3

    1

说明/提示

In the first sample the following road orientation is allowed: , , .

The second sample: , , , , .

The third sample: , , , , .

第一个样例中,以下道路方向是允许的:, , 。

第二个样例:, , , , 。

第三个样例:, , , , 。

输入解题思路,AI测评打分。不知道怎么写?

首页