VTAMASHA- Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Author: Gagandeep Nagpal

Tester: Gagandeep Nagpal

Editorialist: Gagandeep Nagpal

DIFFICULTY:

EASY-MEDIUM.

PREREQUISITES:

Graphs,dfs,bridges.

PROBLEM:

Problems requires you to find those edges which when removed can increase the connected components of the given graph.

QUICK EXPLANATION:

If the edge is a bridge then print “Dj Rocks” else print “Gagan Rocks”

EXPLANATION:

Following a is a psuedo code to find bridges.

time = 0
function DFS(adj[][], disc[], low[], visited[], parent[], AP[], vertex, n)
        visited[vertex] = true
        disc[vertex] = low[vertex] = time+1
        child = 0
        for i = 0 to n
                if adj[vertex][i] == true
                        if visited[i] == false
                                child = child + 1
                                parent[i] = vertex
                                DFS(adj, disc, low, visited, parent, AP, i, n, time+1)
                                low[vertex] = minimum(low[vertex], low[i])
                                if low[i] > disc[vertex]
                                        print vertex, i
                        else if parent[vertex] != i
                                low[vertex] = minimum(low[vertex], disc[i])
2

In the problem statement it should be “increase the connected components”

3

Edited!! thanks