oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

subgraphs Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

subgraphs.html

Problem Description

Given a graph of N nodes and E bidirectional edges, determine how many disjoint subgraphs there are in the graph. For this case, a portion of a graph is considered a subgraph if any 2 node in the portion are connected directly or indirectly. A node without any edges are also considered as a subgraph. Two disjoint subgraph will not have any edges in between any node of the first subgraph and any node of the second subgraph.

The nodes are labelled from 0 to N - 1 and there will not be 2 edges between any 2 pairs of nodes.

Input

2 integers, N then E

E lines consisting of 2 integers each, A and B. 0 ≤ A < B < N.

Output

A single integer, which is the number of disjoint subgraphs.

Limits

Subtask 1 (45%): N = 1000, 0 ≤ E ≤ 10000.

Subtask 2 (55%): N = 1000000, 0 ≤ E ≤ 1000000.

Subtask 3 (0%): As per sample testcases

Sample Testcase 1

Input:

5 3
1 2
3 4
4 0

Output:

2

Explanation:
The graph above contains 2 disjoint subgraphs: {1, 2} and {0, 3, 4}

Sample Testcase 2

Input:

5 4
0 1
1 2
2 3
3 4

Output:

1

Tags

Raffles Cat Helping Practice Contest 2013, Graph Theory, Union Find Disjoint Set

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
145202s64MBMinimum
255202s64MBMinimum
3022s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o subgraphs -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.