You have:

Number of vertices N
K restrictions of form (a,b) that vertices ai and bi cannot be in the same connected component.
an ordered list of M edges (c,d)
The task is to add each of the M edges to the graph according to the order specified in the list, unless it violates any of the K restrictions.
Return the number of edges added to the graph.

For example:
Number of vertices = 4
K restrictions = {(1,4)}
M edges = {(1,2),(2,3),(3,4),(1,3)}

These edges will be added: {(1,2),(2,3),(1,3)}

class Edge {
public int a;
public int b;
public Edge (int a, int b) { … }
}

I was able to solve it using BFS but the interviewer was looking for optimized solution. Any takers?