codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1253D.md (1826B)


      1 Source: https://codeforces.com/problemset/problem/1253/D
      2 
      3 D. Harmonious Graph
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You're given an undirected graph with $n$ nodes and $m$ edges. Nodes are numbered from $1$ to $n$.
     22 
     23 The graph is considered harmonious if and only if the following property holds:
     24 
     25 * For every triple of integers $(l, m, r)$ such that $1 \le l \lt m \lt r \le n$, if there exists a path going from node $l$ to node $r$, then there exists a path going from node $l$ to node $m$.
     26 
     27 In other words, in a harmonious graph, if from a node $l$ we can reach a node $r$ through edges ($l \lt r$), then we should able to reach nodes $(l+1), (l+2), \ldots, (r-1)$ too.
     28 
     29 What is the minimum number of edges we need to add to make the graph harmonious?
     30 
     31 Input
     32 
     33 The first line contains two integers $n$ and $m$ ($3 \le n \le 200\ 000$ and $1 \le m \le 200\ 000$).
     34 
     35 The $i$-th of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$), that mean that there's an edge between nodes $u$ and $v$.
     36 
     37 It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes).
     38 
     39 Output
     40 
     41 Print the minimum number of edges we have to add to the graph to make it harmonious.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 14 8
     49 1 2
     50 2 7
     51 3 4
     52 6 3
     53 5 7
     54 3 8
     55 6 8
     56 11 12
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 1
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 200000 3
     69 7 9
     70 9 8
     71 4 5
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 0
     78 ```
     79 
     80 Note
     81 
     82 In the first example, the given graph is not harmonious (for instance, $1 \lt 6 \lt 7$, node $1$ can reach node $7$ through the path $1 \rightarrow 2 \rightarrow 7$, but node $1$ can't reach node $6$). However adding the edge $(2, 4)$ is sufficient to make it harmonious.
     83 
     84 In the second example, the given graph is already harmonious.