Given an undirected graph with n vertices. There are m sets of edges in this graph, the \(i^{th}\) set is represented by 2 integers \((l_i,r_i)\) meaning that there are edges \((l_i,r_i),(l_i + 1,r_i - 1), \dots, (r_i,l_i)\) in the graph.
Find the number of connected components in this graph.
\(\textbf{Input}\)
The first line contains 2 integers - \(n,m\) \((1 \le n \le 500 \; 000, 1 \le m \le 100 \; 000)\).
The next m lines contain 2 integers - \(l_i,r_i\) \((1 \le l_i \le r_i \le n)\).
\(\textbf{Output}\)
Output the number of connected components in the graph.
The edges are \((1,3),(2,2),(3,1),(2,5),(3,4),(4,3),(5,2)\), so there are 2 connected components: \((1,3,4),(2,5)\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor