Pourquoi ce code ne fonctionne pas sur hackerrank?

Question

Je résoudre un problème sur HackerRank, vous pouvez lire que ON- https://www.hackerrank.com/challenges/journey-to-the-moon

sortie est pas correcte en utilisant le code suivant

J'ai mis en place toutes les structures de données requises dans ce code et essayé de créer une matrice de tailles composants connectés.

import java.io.*; 
import java.util.*; 



public class Solution { 
public static void main(String[] args) throws Exception{ 

    BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));  
    String[] temp = bfr.readLine().split(" "); 
    int N = Integer.parseInt(temp[0]); 
    int I = Integer.parseInt(temp[1]); 
    Solution sol=new Solution(); 
    Graph g = sol.new Graph(N); 


    for(int i = 0; i < I; i++){ 
     temp = bfr.readLine().split(" "); 
     int a = Integer.parseInt(temp[0]); 
     int b = Integer.parseInt(temp[1]); 
     g.addEdge(a,b); 
     // Store a and b in an appropriate data structure of your choice 
    } 
    CC ccg=sol.new CC(g); 
    int len=ccg.getComp(); 

    long combinations = 0; 
    for(int k=0;k<len;k++){ 
     if(k==0){ 
      combinations+=ccg.getNum(k); 
     }else{ 
      combinations*=ccg.getNum(k); 
     } 
    } 
    // Compute the final answer - the number of combinations 

    System.out.println(combinations); 
    } 

    class Graph{ 
     final int s; 
     Bag[] adj; 
     public Graph(int si){ 
      s=si; 
      adj=new Bag[s]; 
      for(int i=0;i<si;i++){ 
       adj[i]=new Bag(); 
      } 
     } 
     public void addEdge(int i,int j){ 
      adj[i].add(j); 
      adj[j].add(i); 
     } 

     public int graphSize(){ 
      return s; 
     } 

     public Iterable<Integer> adj(int v){ 
      return adj[v]; 
     } 
    } 
    class Bag implements Iterable<Integer>{ 

    Node first; 
     int size=0; 
     final class Node{ 
      int i; 
      Node next; 
     } 
     public void add(int x){ 
      Node old=first; 
      first=new Node(); 
      first.i=x; 
      first.next=old; 
      size++; 
     } 
     public int getSize(){ 
      return size; 
     } 
     public Iterator<Integer> iterator() { 
      // TODO Auto-generated method stub 
      return new ListIterator(); 
     } 

     public class ListIterator implements Iterator<Integer>{ 
      private Node current=first; 
      public boolean hasNext(){ 
       return current!=null; 
      } 
      public void remove(){} 
      public Integer next(){ 
       int i=current.i; 
       current=current.next; 
       return i; 
      } 
     } 

    } 

    class CC{ 
     private boolean[] marked; 
     private int[] id; 
     private int[] comp; 
     private int count=0; 

     public CC(Graph g){ 
      int i=g.graphSize(); 
      marked=new boolean[i]; 
      id=new int[i]; 
      comp=new int[i]; 
      for(int j=0;j<i;j++){ 
       comp[j]=0; 
      } 

      for(int v=0;v<i;v++){ 
       if(!marked[v]){ 
        dfs(g,v); 
        count++; 
       } 
       comp[count]=comp[count]+1; 
      } 

     } 
     public int getComp(){ 
      return count; 
     } 
     public int getNum(int i){ 
      return comp[i]; 
     } 
     private void dfs(Graph g,int v){ 
      marked[v]=true; 
      id[v]=count; 
      for(int w:g.adj[v]){ 
       if(!marked[w]){ 
        dfs(g,w); 
       } 
      } 
     } 
    } 




    } 

Answer 1

J'ai effectué quelques tests de votre programme.

Dans toutes les exécutions votre programme a imprimé 0. Alors que 0 est la sortie correcte dans certains cas, ce n'était pas la bonne sortie dans tous les cas. Donc, cela pourrait être une raison pour Hackerrank de réduire votre programme. Exemple d'entrée:

3 1 
0 2 

que je voulais dire ce pour décrire 2 nations avec les astronautes 0 et 2 provenant d'une nation et l'astronaute 1 des autres nations. Sortie prévue: 2 Sortie réelle de votre programme: 0.

(J'ai édité ce paragraphe.) Il semble que si toutes les paires ont A égal à B, vous obtiendrez un ArrayIndexOutOfBoundsException. Par exemple:

1 1 
0 0 

Je ne vois rien dans les règles HackerRank interdisant A == B, donc je suppose que vous devriez prendre en compte. Comme je l'ai dit dans un commentaire, je ne suis pas en train de creuser dans votre programme pour comprendre pourquoi il s'est comporté comme je l'ai décrit; Je n'ai fait que vous observer et vous rendre compte. Je vais laisser le débogage à vous-même.