report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
  • Problem
  • Submit
  • Results
Connected component - MarisaOJ: Marisa Online Judge

Connected component

Time limit: 1000 ms
Memory limit: 256 MB
Given a undirected graph of $n$ vertices and $m$ edges. Count the number of connected components in this graph. ### Input - The first line contains 2 integers $n, m$. - The next $m$ lines, each line contains 2 integers $u, v$, there is an edge between those vertices. ### Output - Print the number of connect components. ### Constraints - $1 \le n, m \le 10^5$. - $1 \le u, v \le 10^5$. ### Example Input: ``` 5 4 1 2 1 3 2 3 4 5 ``` Output: ``` 2 ```
BFS / DFS
Connected component
Shortest path
Finding the path
Path on binary matrix
Garden
Operations on number
Bipartite graph
Tom and Jerry
Festival 1
Bamboo Forest of the Lost
Radar
Festival 2
Go
Escape from... dolls
Long leg
Lexicographically smallest path
Graph coloring
Topic
Graph
Rating 800
Solution (1) Solution