Flight Vocher hackerearth solution

Flight Vocher hackerearth solution

  December 09, 2018    

---

Problem:
There are alot of passengers in a flight we need to provide voucher to every kth passenger but we dont know their sequence.

We are given connections that x&y are sitting in same row.
give voucher to every kth passenger sorted according to their id.

Solution :
Idea is to use GRaph BFS

import java.util.*;
import java.lang.*;
class graphbfshackr
{
  static int count=0;
  static ArrayList<Integer> token=new ArrayList<>();
private static int v; // no. of the vertex
private static LinkedList<Integer> arr[];
graphbfshackr(int V)
{
this.v=V;
arr=new LinkedList[v];
for(int i=0;i<V;i++)
arr[i]=new LinkedList();
}
void addEdge(int x,int y)
{
arr[x].add(y);
}
void BFS(int x,boolean visited[],int gap)
{
LinkedList<Integer> q=new LinkedList<Integer>();
q.add(x);
visited[x]=true;
    ArrayList<Integer> cur=new ArrayList<>();
while(!q.isEmpty())
{
x=q.poll();
    //  System.out.print(" visiting "+x);
      cur.add(x);
Iterator<Integer> itr=arr[x].listIterator();
while(itr.hasNext())
{
int temp=(int)itr.next();
if(!visited[temp])
{
q.add(temp);
visited[temp]=true;
}
}
}
    Collections.sort(cur);
    for(int i=gap-1;i<cur.size();i+=gap)
    {
      ++count;
      token.add(cur.get(i));}
}
public static void main(String args[])
{
    Scanner ab=new Scanner(System.in);
  int n=ab.nextInt();
  int e=ab.nextInt();
  int gap=ab.nextInt();
    HashSet<Integer> edges=new HashSet<>();
    graphbfshackr g=new graphbfshackr(n+1);
for(int i=0;i<e;++i)
{
    int x=ab.nextInt();
    int y=ab.nextInt();
    edges.add(x);
    edges.add(y);
  g.addEdge(x,y);
  g.addEdge(y,x);}
      boolean visited[]=new boolean[v];
      for(int i=1;i<=n;++i)
      if(!visited[i] && edges.contains(i))
        g.BFS(i,visited,gap);
        int cur=0;
        for(int i=1;i<=n;++i)
        {
          if(!edges.contains(i))
          {
            ++cur;
            if(cur==gap)
            {
              token.add(i);
              cur=0;
              ++count;
            }
          }
        }
        System.out.println(count);
        Collections.sort(token);
        for(int i:token)
        System.out.print(i+" ");
}
}