Pairing problem-Graph

#1

Q-There are N cities numbered from 0 to N-1. You have to choose 2 cities such that there is no path from first city to second city .
You are given information in the form of M pairs (X,Y) i.e there is an undirected road between city X and city Y.
Find out the number of ways in which cities can be chosen.

Input Format:
The first line contains two integers, N and M separated by a single space. M lines follow. Each line contains integers separated by a single space X and Y denoting road between X and Y.

Constraints:
1 <= N <= 100000 1 <= M <= 100000 0 <= X,Y <= N-1

Output Format
An integer that denotes the number of permissible ways to choose a pair of cities.
CODE-https://ide.codingblocks.com/s/166958

Please help me count the number of nodes in each components

#2

inside your dfs function, pushback components inside the for loop else you’ll always miss then and get 0 as answer

1 Like
#5

Thanks I’m able to count the number of nodes in a component.
but I’m still getting WA can you pls provide some hint what should I change in my code
code-https://ide.codingblocks.com/s/167505

#6

Lets debug this. How?
First check if number of components you are getting is correct for respective components. If its correct then just take ll int and multiply as required.
If thats wrong ,check what are you missing by printing your visited array.

1 Like
#7

I printed the number of nodes in the components for the following test case
7 4
0 1
2 3
0 4
5 6
and got 2=number of component(but its 3 in the above case)
3 2 1 as the number of nodes in each component(which is again wrong)
can you please help me with the code.

#8

See, i want you to debug it. When you know number of components are not right, try printing the components you have got. You’ll come to know whats the problem. Keep printing step by step to know where the problem is.
Its just about writing debugging lines.

#9

thanks I figured it out:grin:

1 Like
#10

Great!
Now you’ll be able to solve such problems yourself in future! :sunglasses:

1 Like
#11

Send me a question link