蓝桥幼儿园
题目描述
蓝桥幼儿园的学生是如此的天真无邪，以至于对他们来说，朋友的朋友就是自己的朋友。
小明是蓝桥幼儿园的老师，这天他决定为学生们举办一个交友活动，活动规则如下：
小明会用红绳连接两名学生，被连中的两个学生将成为朋友。
小明想让所有学生都互相成为朋友，但是蓝桥幼儿园的学生实在太多了，他无法用肉眼判断某两个学生是否为朋友。于是他起来了作为编程大师的你，请你帮忙写程序判断某两个学生是否为朋友（默认自己和自己也是朋友）。
输入描述
第 11 行包含两个正整数 N,M，其中 N 表示蓝桥幼儿园的学生数量，学生的编号分别为 1∼N。
之后的第 2∼M+1 行每行输入三个整数，op,x,y
如果 op=1op=1，表示小明用红绳连接了学生 xx 和学生 yy 。
如果 op=2op=2，请你回答小明学生 xx 和 学生 yy 是否为朋友。
1≤N,M≤2×10^5，1≤x,y≤N
输出描述
对于每个 op=2的输入，如果 x 和 y 是朋友，则输出一行 YES，否则输出一行 NO。
输入输出样例
示例 1
输入
5 5
2 1 2
1 1 3
2 1 3
1 2 3
2 1 2
输出
NO
YES
YES
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Main {static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws IOException {String[] s = br.readLine().split(" ");int n=Integer.parseInt(s[0]);int m=Integer.parseInt(s[1]);UnionFind u=new UnionFind(n+1);while (m>0){s=br.readLine().split(" ");if (Integer.parseInt(s[0])==1){u.union(Integer.parseInt(s[1]),Integer.parseInt(s[2]));}else {if (u.isConnected(Integer.parseInt(s[1]),Integer.parseInt(s[2]))) System.out.println("YES");else System.out.println("NO");}m--;}}}class UnionFind{private int count;private int[] parent;public UnionFind(int count){this.count=count;parent=new int[count];for (int i=0;i<count;i++){parent[i]=i;}}public void union(int a,int b){int parentA=find(a);int parentB=find(b);if (parentA==parentB) return;parent[parentA]=parentB;count--;}public boolean isConnected(int a,int b){return find(a)==find(b);}public int find(int x){if (x==parent[x]) {return x;}else {parent[x]=find(parent[x]);return parent[x];}}public int getCount(){return this.count;}
}
import java.io.*;
import java.util.Scanner;public class Main {static int[] f;public static void main(String[] args) throws IOException {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();f=new int[n+1];for (int i=1;i<=n;i++){f[i]=i;}for (int i=0;i<m;i++){int op=sc.nextInt();int x=sc.nextInt();int y=sc.nextInt();if (op==1){int fi=find(x);int fj=find(y);f[fi]=fj;}else {if (find(x)==find(y)){System.out.println("YES");}else {System.out.println("NO");}}}}public static int find(int x){if (x==f[x]) {return x;}else {f[x]=find(f[x]);return f[x];}}
}蓝桥侦探
题目描述
小明是蓝桥王国的侦探。
这天，他接收到一个任务，任务的名字叫分辨是非，具体如下：
蓝桥皇宫的国宝被人偷了，犯罪嫌疑人锁定在 N 个大臣之中，他们的编号分别为 1∼N
在案发时这 N 个大臣要么在大厅1，要么在大厅2，但具体在哪个大厅他们也不记得了。
审讯完他们之后，小明把他们的提供的信息按顺序记了下来，一共 M 条，形式如下：
x y，表示大臣 xx 提供的信息，信息内容为：案发时他和大臣 yy 不在一个大厅。
小明喜欢按顺序读信息，他会根据信息内容尽可能对案发时大臣的位置进行编排。
他推理得出第一个与先前信息产生矛盾的信息提出者就是偷窃者，但推理的过程已经耗费了他全部的脑力，他筋疲力尽的睡了过去。作为他的侦探助手，请你帮助他找出偷窃者！
输入描述
第 1 行包含两个正整数 N,M，分别表示大臣的数量和口供的数量。
之后的第 2∼M+1行每行输入两个整数 x,y，表示口供的信息。
1≤N,M≤5×10^5，1≤x,y≤N
输出描述
输出仅一行，包含一个正整数，表示偷窃者的编号。
输入输出样例
输入
4 5
1 2
1 3
2 3
3 4
1 4
输出
2
import java.io.*;public class Main {static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws IOException {String[] s = br.readLine().split(" ");int n=Integer.parseInt(s[0]);int m=Integer.parseInt(s[1]);UnionFind u=new UnionFind(2*n+1);while (m>0){s=br.readLine().split(" ");if (u.find(Integer.parseInt(s[0]))!=u.find(Integer.parseInt(s[1]))){u.union(Integer.parseInt(s[0]),Integer.parseInt(s[1])+n);u.union(Integer.parseInt(s[0])+n,Integer.parseInt(s[1]));}else {System.out.println(Integer.parseInt(s[0]));return;}m--;}}
}class UnionFind{private int count;private int[] parent;public UnionFind(int count){this.count=count;parent=new int[count];for (int i=0;i<count;i++){parent[i]=i;}}public void union(int a,int b){int parentA=find(a);int parentB=find(b);if (parentA==parentB) return;parent[parentA]=parentB;count--;}public boolean isConnected(int a,int b){return find(a)==find(b);}public int find(int x){if (x==parent[x]) {return x;}else {parent[x]=find(parent[x]);return parent[x];}}public int getCount(){return this.count;}
}
蓝桥部队
题目描述
小明是蓝桥部队的长官，他的班上有 N 名军人和 1 名军师。
这天，N 名军人在操场上站成一排，起初编号为 i 的军人站在第 i列。
作为长官，小明可以对军人和军师下达 M 条命令，命令有两种类型，格式如下：
1 x y，让军人 x 所在列的所有人作为一个整体移动到和军人 y 所在列的后面，使两列合并为一列。
2 x y，询问军师军人 x 和军人 y 是否站在同一列。若是，则军师要回应小明 x,y 之间有多少人，否则军师要回应 −1。
你就是小明的军师，请你回答小明的每个询问。
输入描述
输入第 1 行包含两个正整数 N,M，分别表示军人的数量和小明的命令条数。
第 2∼M+1 行每行表示一条命令。
2≤N≤10^5，1≤M≤3×10 5，1≤x,y≤N
输出描述
对于每个询问，输出一行表示答案。
输入输出样例
输入
3 5
2 1 2
1 2 1
2 1 2
1 1 3
2 2 3
输出
-1
0
1
import java.io.*;
import java.util.Arrays;
import java.util.Scanner;public class Main {static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws IOException {String[] s = br.readLine().split(" ");int n=Integer.parseInt(s[0]);int m=Integer.parseInt(s[1]);UF u=new UF(n+1);for (int i=0;i<m;i++){s=br.readLine().split(" ");int op=Integer.parseInt(s[0]);int x=Integer.parseInt(s[1]);int y=Integer.parseInt(s[2]);if (op==1){u.merge(y,x);}else {out.println(u.dist(x,y));}}out.flush();}
}class UF{//d表示到根节点的距离，siz表示这个连通块有多少个元素int[] f,d,siz;public UF(int n){f=new int[n];d=new int[n];siz=new int[n];for (int i=1;i<n;i++){f[i]=i;}Arrays.fill(siz,1);}int find(int x){if (x==f[x]) return f[x];int root=find(f[x]);d[x]+=d[f[x]];return f[x]=root;}boolean same(int x,int y){return find(x)==find(y);}boolean merge(int x,int y){x=find(x);y=find(y);if (x==y) return false;d[y]+=siz[x];siz[x]+=siz[y];f[y]=x;return true;}int size(int x){return siz[find(x)];}int dist(int x,int y){if (!same(x,y)) return -1;return Math.abs(d[x]-d[y])-1;}
}
