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.
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
Editorial