### 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])
```