Javaの要素ペアのリストからセットを形成するコード

Question

私は、（1,2）（3,4）のような要素のペアのリストがあり、重複が存在しない場合、ペア（p、q） p！= q。 単純なコードを使用してこの要素からセットを作成する方法（単純な方法でコードを書くことができない限り、私は分離した集合や共用体のようなデータ構造を使用するつもりはありません。 例：（1,2）（2,4）（5,6）（4,7）（3,5）は、出力する必要があります。 {1,2,4,7}および{3,5,6}

List<Set<Integer>> list = new ArrayList<>(); 
    for(String s : pairs){ 
     String[] values = s.split(" "); 
     Integer val1 = Integer.parseInt(values[0]); 
     Integer val2 = Integer.parseInt(values[1]); 

     Set<Integer> pairSet = new HashSet<>(); 
     pairSet.add(val1); 
     pairSet.add(val2); 

     boolean exists = false; 
     for(Set<Integer> set : list){ 
      if(set.contains(val1) || set.contains(val2)) { 
       set.addAll(pairSet); 
       exists = true; 
       break; 
      } 
     } 
     if(!exists) 
      list.add(pairSet); 
    } 

これは間違ったアプローチです。シーケンス（1 2）（3 4）と（2 3）を得ると、出力は{1,2,3}と{3,4}になります。

これは、セットのリストが {1,2}、次に{3,4}のように作成され、次にペア（2 3）が来るときに2つのセットをマージしないために発生します。

//loop -> s1 = find val1 
    //loop -> s2 = find val2 
    if s1 != null and s2 != null //merge s1 and s2 
    if(s1 == null && s2 != null) //add val1 and val2 to s2 
    if(s1 != null && s2 == null) //add val1 and val2 to s1 
    if(both null) create a new set of val1 and val2 

あまりにも多くのループと条件：

Iが第1の値をチェックするためのコードを書くことができ、任意のセット内に存在しているがS1と他の値のために、同じマージ次にS2を言うと言います。より単純なソリューションですか？

Answer 1

グラフのエッジの説明として各ペアを考えると、シンプルなDFSがこのトリックを行います。

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

class Solution 
{ 
    static int n = 1000000; 
    static ArrayList< ArrayList<Integer> > adj = new ArrayList<ArrayList<Integer>>(); 
    static Boolean[] visited = new Boolean[n]; 

public static void main (String[] args) throws java.lang.Exception 
{ 
    String input[] = {"1 2", "3 4", "2 3","5 6"}; 
    System.out.println(answer(input)); 
} 

public static void dfs(int u,Set<Integer> res){ 
    visited[u] = true; 
    for(int e : adj.get(u)){ 
     if(!visited[e]) 
      dfs(e,res); 
    } 
    res.add(u); 
} 
static void init(){ 
    for(int i = 0 ; i < n ; i++) 
     adj.add(new ArrayList<Integer>()); 
} 

public static List<Set<Integer>> answer(String[] pairs){ 
    init(); 
    List<Set<Integer>> list = new LinkedList<>(); 
    Set<Integer> elements = new HashSet<Integer>(); 
    for(int i = 0 ; i < pairs.length ; i++){ 
    String[] splitted = pairs[i].split(" "); 
    int u = Integer.parseInt(splitted[0]); 
    int v = Integer.parseInt(splitted[1]); 
     adj.get(u).add(v); 
     adj.get(v).add(u); 
     visited[u] = visited[v] = false; 
     elements.add(u);elements.add(v); 
    } 

    for(int e : elements){ 
     if(!visited[e]){ 
      Set<Integer> tmp = new HashSet<Integer>(); 
      dfs(e,tmp); 
      list.add(tmp); 
     } 
    } 
    return list; 
} 
} 

Answer 2

改訂版：ここ

、私はそれはあなたにナイーブなアプローチと呼ばものを使用して作られています

public static List<Set<Integer>> answer(String[] pairs){ 

    List<Set<Integer>> list = new LinkedList<>(); 
    // For each pair, separate the numbers 
    //Initialize with initial set 
    Set<Integer> init = new HashSet<>(); 
    String[] splitted = pairs[0].split(" "); 
    init.add(Integer.parseInt(splitted[0])); 
    init.add(Integer.parseInt(splitted[1])); 

    list.add(init); 

    // To be used to maintain set record ahead 
    List<Set<Integer>> setsRecord = new LinkedList<>(); 

    boolean found = false; 
    Integer i1, i2; 
    for(String s : pairs){ 
     i1 = Integer.parseInt((splitted = s.split(" "))[0]); 
     i2 = i2 = Integer.parseInt(splitted[1]); 
     for(Set<Integer> set : list){ 
      if(set.contains(i1) || set.contains(i2)){ 
       // If element has already been found in a set, create a common set 
       if(setsRecord.size() >= 1){ 
        setsRecord.get(0).addAll(set); 
        // And remove this set 
        list.remove(set); 
       } 
       else{ 
        set.add(i1); 
        set.add(i2); 
        // Maintain a record of this set 
        setsRecord.add(set); 
       } 
       found = true; 
      } 
     } 
     // Empty the temporary set record 
     setsRecord.clear(); 

     if(!found){ 
      Set<Integer> newSet = new HashSet<Integer>(); 
      newSet.add(i1); 
      newSet.add(i2); 
      list.add(newSet); 
     } 
     found = false; 
    } 
    return list; 
} 

Demo.

Answer 3

私は解決策を掲載しています。誰かがこのコードを簡単にすることができれば、それは素晴らしいことです。 TIAは

 static void formSet(String[] pairs) { 

    List<Set<Integer>> list = new ArrayList<>(); 
    for(String s : pairs){ 
     String[] values = s.split(" "); 
     Integer val1 = Integer.parseInt(values[0]); 
     Integer val2 = Integer.parseInt(values[1]); 

     Set<Integer> pairSet = new HashSet<>(); 
     pairSet.add(val1); 
     pairSet.add(val2); 

     Set<Integer> val1_set = null, val2_set = null; 
     for(Set<Integer> set : list){ 
      if(set.contains(val1)) { 
       val1_set = set; 
      } 

      if(set.contains(val2)) { 
       val2_set = set; 
      } 
     } 
     if(val1_set == null && val2_set == null) 
      list.add(pairSet); 
     if(val1_set != null && val2_set == null) 
      val1_set.addAll(pairSet); 
     if(val1_set == null && val2_set != null) 
      val2_set.addAll(pairSet); 
     if(val1_set != null && val2_set != null){ 
      list.remove(val2_set); 
      val1_set.addAll(val2_set); 
     } 
    } 

    for(Set<Integer> set : list){ 
     System.out.println(set); 
    } 
} 

ここにコードレビューへのリンクです： https://codereview.stackexchange.com/questions/163301/forming-a-set-from-a-pair-of-numbers