频繁更新新边时检查两个节点是否连接

Question

人们在社交网络中相互联系。人 I 和人 J 之间的连接表示为 C I J。当属于不同社区的两个人连接时，净效果是 I 和 J 所属的两个社区合并。你的任务是找出两个人是否在同一组中。

输入格式

社交网络总人数（N）查询

C I J，连接I和J

Q K L，查询社区，看K和L是否属于同一个群 -1表示输入结束。

输出格式

对于每个查询 Q，如果 K 和 L 在同一组中，则打印 "Yes" 否则打印 "No".

示例测试用例

输出

Yes
Yes
Yes
Yes
No

所以我认为这是一个基本的深度优先搜索来找出两个节点之间的 link..但是我已经过了一段时间 limit.Is 有一个简单的方法吗？还有我如何确定我的代码的运行时间。

 public class isotope {
    static List<Integer>[] list;
    static boolean[] vis;
    static int end;

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        solve(in, out);
        out.close();
    }

    static void solve(InputReader in, PrintWriter out) {
        int n = in.nextInt();
        list = new List[n + 1];
        for (int i = 0; i < list.length; i++) list[i] = new ArrayList<>();
        while (true) {
            String[] temp = in.readLine().split(" ");
            //System.out.println(Arrays.toString(temp));
            if (temp[0].equals("-1")) return;
            //System.out.println(temp[0]);
            if (temp[0].equals("C")) {
                int x = Integer.parseInt(temp[1]);
                int y = Integer.parseInt(temp[2]);
                list[x].add(y);
                list[y].add(x);
            } else if (temp[0].equals("Q")) {
                vis = new boolean[n + 1];
                int a = Integer.parseInt(temp[1]);
                int b = Integer.parseInt(temp[2]);

                end = b;
                if (depthfs(a)) out.println("Yes");
                else out.println("No");
            }
        }

    }

    depthfs(int start) {
        vis[start] = true;
        int k = 0;
        Stack<Integer> stk = new Stack<>();
        stk.push(start);
        while (!stk.isEmpty()) {
            int x = stk.pop();
            for (int i = 0; i < list[x].size(); i++) {

                //System.out.println("LIST "+list[x].get(i));
                //System.out.println(stk);//if(++k>10)return true;
                if (list[x].get(i) == end) {
                    //System.out.println("ANSWER IS "+end);
                    return true;
                } else if (!vis[list[x].get(i)]) {
                    vis[list[x].get(i)] = true;
                    stk.push(list[x].get(i));
                }
            }
        }
        return false;
    }

Answer 1

我认为您的数据结构效率低下，您不应该拥有同一网络的 2 个副本。这是一个使用 Map 和多个 Set 的示例。每个Set对应一个网络，而Map则对应一个节点（key）和一个网络（value）。

虽然在我的答案末尾提供了完整代码，但我将在此处详细介绍 2 种主要方法（isIn 和 addConnection）：

private static List <Set<Integer>> nodes ;

第一件事是用初始网络（每个节点在自己的网络中）初始化nodes。假设 N 个节点（您读取的第一个值）：

// Nodes number goes from 1 to N, not 0 to N - 1, but I don't want to deal with this
// so I will add a fake 0 node.
nodes = new ArrayList <Set <Integer>> () ;
for (int i = 0 ; i < N + 1 ; ++i) {
    Set <Integer> s = new HashSet <Integer> () ;
    s.add(i) ;
    nodes.add (s) ;
}

所以这里nodes.get(a)就是节点a的网络。如果 a 和 b 在同一个网络上，我们有 nodes.get(a) == nodes.get(b)，注意这里我说的是指针相等，nodes.get(a) 是同一个对象（在内存中） nodes.get(b).

注意：因为你一开始就知道节点总数，而且你的节点是按数字顺序排列的，你可以使用简单的ArrayList代替HashMap.

在

private static boolean isIn (int a, int b) {
    return nodes.get(a).contains(b) ;
}

好吧，这很简单，要检查连接，您需要检查 a 的网络是否包含节点 b。请记住 nodes.get(a) return a 的网络，您还可以检查 nodes.get(b).contains(a).

添加连接

private static void addConnection (int a, int b) {
    Set <Integer> setB = nodes.get(b) ;
    nodes.get(a).addAll (setB) ;
    for (int i = 0 ; i < nodes.size() ; ++i) {
        if (nodes.get(i) == setB) {
            nodes.set(i, nodes.get(a)) ;
        }
    }
}

同样，微不足道：

您检索 b 的网络。
您将 b 网络中的所有节点添加到 a 网络中。
对于b（nodes.get(i) == setB）旧网络中的每个节点，包括b本身，您将网络设置为新网络。

整个代码（未注释）：

import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class NetworkStuff1 {

    private static List <Set<Integer>> nodes ;

    private static boolean isIn (int a, int b) {
        return nodes.get(a).contains(b) ;
    }

    private static void addConnection (int a, int b) {
        Set <Integer> setB = nodes.get(b) ;
        nodes.get(a).addAll (setB) ;
        for (int i = 0 ; i < nodes.size() ; ++i) {
            if (nodes.get(i) == setB) {
                nodes.set(i, nodes.get(a)) ;
            }
        }
    }

    public static void solve (Scanner in, OutputStreamWriter out) throws IOException {
        int N = Integer.parseInt (in.nextLine()) ;
        // Nodes number goes from 1 to N, not 0 to N - 1, but I don't want to deal with this
        // so I add a useless 0 cell in my array.
        nodes = new ArrayList <Set <Integer>> () ;
        for (int i = 0 ; i < N + 1 ; ++i) {
            Set <Integer> s = new HashSet <Integer> () ;
            s.add(i) ;
            nodes.add (s) ;
        }
        while (true) {
            String[] tmp = in.nextLine().split(" ") ;
            if (tmp[0].equals("-1")) {
                break ;
            }
            if (tmp[0].equals("C")) {
                addConnection(Integer.parseInt (tmp[1]), Integer.parseInt (tmp[2])) ;
            }
            else if (tmp[0].equals("Q")){
                if (isIn (Integer.parseInt (tmp[1]), Integer.parseInt (tmp[2]))) {
                    System.out.println("Yes") ;
                }
                else {
                    System.out.println("No") ;
                }
            }
        }
    }

    /**
     * @param args
     * @throws IOException 
     */
    public static void main(String[] args) throws IOException {
        solve (new Scanner(System.in), new OutputStreamWriter(System.out)) ;
    }

}

Answer 2

您可以为此使用联合查找数据结构。为此，union() 和 find() 方法实际上都是 O(1).

用人数初始化结构

如果遇到连接C i j，调用union(i, j)。

如果遇到查询Q i j，输出find(i) == find(j)

频繁更新新边时检查两个节点是否连接

Check if two nodes are connected when updating new edges frequently

algorithm

depth-first-search