南宁在百度上建网站/免费的网站推广在线推广

java实现oj214题朋友圈

先看题目：

本题的基本思路就是利用并查集来解，难度不大。
先来看一下并查集的实现：
并查集的实现方式有很多种，这里采用的是路径压缩方法，这种方法的目的是为了避免树形结构退化成链表结构，会大大影响效率。
代码如下：

public class UnionSet {private int[] fa;private int[] size;private int n;public UnionSet(int n) {this.n = n;fa = new int[n + 1];size = new int[n + 1];for (int i = 0; i <= n; i++) {fa[i] = i;size[i] = 1;}}public int find(int x) {if(fa[x] == x) return x;int root = find(fa[x]);fa[x] = root;return root;}public void merge(int a, int b) {int ra = find(a),rb = find(b);if(size[ra] < size[rb]){fa[ra] = rb;size[rb] += size[ra];}else{fa[rb] = ra;size[ra] += size[rb];}}
}

解决这道题就是当a=1时，将b与c合并起来，当a=2时判断b与c的根是否相等，代码如下：

public class Main{static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}public static void main(String[] args) throws NumberFormatException, IOException{int n,m;n = nextInt();m = nextInt();UnionSet u = new UnionSet(n);for(int i=0;i<m;i++){int a,b,c;a = nextInt();b = nextInt();c = nextInt();switch(a){case 1:u.merge(b,c);break;case 2:if(u.find(b) == u.find(c)){out.println("Yes");out.flush();}else{out.println("No");out.flush();}break;}}}
}

可能会遇到的问题：
在OJ中用Sanccer进行输入，用System.out.println进行输出可能会出现超时，这里应当采用快速输入输出：

    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}