# how to proceed in this graph question

Recently I saw this question , and I got the idea that it will be solved using bfs/dfs , but couldn’t reach the final working algorithm .Can someone help me with this?

Suppose there is a city of N towns and M bidirectional roads where a strict mayor has set of certain rules.

Rule 1: men can walk only on roads marked by type 1 or 3.
Rule 2: women can walk only on roads marked by type 2 or 3.

He now thought to renovate the city by reconstructing some roads but with a condition that the normal routine of the citizen should not be hampered. You are hired to do the duty. So he asks you – What is the maximum number of roads it’s possible to destroy that the city will be still connected to both men and women?

The city is said to be connected if it’s still possible to travel from town X to town Y using the existing roads.

Input
The first line contains 2 space-separated integers: N and M.
Each of the following M lines contains description of one edge: three different space-separated integers: A, B, and C.
A and B are different and from 1 to N each and denote numbers of vertices that are connected by this edge. C denotes the type of this edge.

Output
For each test case output one integer - the maximal number of roads it’s possible to destroy or -1 if the town is not connected initially for both men and women.

Constraints
1 <= N <= 1000
1 <= M <= 10000
1 <= A, B <= N
1 <= C <= 3

1 Like

do the DSU separately for men and then women … for each Union of type 3 … you can do it twice one each for men and women … then check for the connected components of men first and if it does have a component , go for women graph …
my implementation :- http://ideone.com/ErzVJl

5 Likes

provide some test cases bro