PROBLEM LINK:
Setter: debrc
Tester: mishra_roshan
Editorialist: debrc
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Basic observations, Set
PROBLEM:
Given A number of nodes and B number of edges, find out if Node 1 and Node A are exactly two edges away.
EXPLANATION
If there is at least one common node to which Node 1 and Node A both are connected through a edge, then both the node are exactly two edges away.
So we can make two sets,
one set contains the nodes to which Node 1 is connected and
one set contains the nodes to which Node A is connected.
If the bitwise and of both the sets leads to True then there has to be at least one common node in both the sets.
Otherwise, no common nodes are there, hence Node 1 and Node A are not two edges away.
TIME COMPLEXITY
Time complexity is O(A) for making the set.
SOLUTIONS:
Setter's Solution
Python
a,b=map(int,input().split())
node1,noden=[],[]
for i in range(b):
u,v=map(int,input().split())
if u==1:
node1.append(v)
if v==a:
noden.append(u)
if set(node1)&set(noden):
print("YES")
else:
print("NO")
Tester's Solution
Java
import java.util.*;
public class Main {
static ArrayList<ArrayList<Integer>> adj=new ArrayList<ArrayList<Integer>>();
static void bfs(int node,int[] dis){
Queue<Integer> q=new LinkedList<Integer>();
dis[node]=0;
q.add(node);
while(q.size()>0){
int curr=q.poll();
for(int child:adj.get(curr)){
if(dis[child]==-1){
dis[child]=dis[curr]+1;
q.add(child);
}
}
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
int b=sc.nextInt();
for(int i=0;i<=a;i++)
adj.add(new ArrayList<Integer>());
for(int i=1;i<=b;i++){
int u=sc.nextInt();
int v=sc.nextInt();
adj.get(u).add(v);
adj.get(v).add(u);
}
int[] dis=new int[a+1];
Arrays.fill(dis,-1);
bfs(1,dis);
if(dis[a]>2 || dis[a]==-1)
System.out.println("NO");
else
System.out.println("YES");
}
}
Feel free to Share your approach.
Suggestions are welcomed as always had been.