Classic task
Practice
4.8 (12 votes)
Ad Hoc
Dsu
Data structures
Disjoint data structures
Disjoint set
Hard
難しい
Problem
71% Success 2658 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
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
41 votes
Tags:
ApprovedData StructuresDisjoint setHardImplementationOpen
Points:50
6 votes
Tags:
Data StructuresDisjoint Data StructuresDisjoint SetDisjoint setHard
Points:50
5 votes
Tags:
AlgorithmsApprovedData StructuresDisjoint setHardOpen
Editorial
Login to unlock the editorial