Classic task
Practice
4.8 (12 votes)
Ad Hoc
Dsu
Data structures
Disjoint data structures
Disjoint set
Hard
難しい
Problem
71% Success 2657 Attempts 50 Points 2s Time Limit 256MB Memory 1024 KB Max Code

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.

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

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
5 votes
Tags:
AlgorithmsApprovedData StructuresDisjoint setHardOpen
Points:50
6 votes
Tags:
Data StructuresDisjoint Data StructuresDisjoint SetDisjoint setHard
Points:50
1 votes
Tags:
Data StructuresDisjoint Data StructuresDisjoint SetHard