DAY55-图论-并查集
并查集理论底子并查集理论底子 | 代码随想录 (programmercarl.com)
kama107.探求存在的路径
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int[] father = new int;
init(father); //初始化
for(int i=0;i<m;i++) {
int x = scan.nextInt();
int y = scan.nextInt();
join(father,x,y);
}
int res1 = scan.nextInt();
int res2 = scan.nextInt();
if(isSame(father,res1,res2))System.out.println(1);
else System.out.println(0);
scan.close();
}
/**
* 查找根节点,并进行路径压缩
* @param father
* @param x
* @param y
* @return
*/
public static int findFather(int[]father,int x) {
if(father==x)return x;
else return father=findFather(father,father);
}
/**
* 初始化
* @param father
*/
public static void init(int[] father) {
for(int i=1;i<father.length;i++) {
father=i;
}
}
/**
* 判断是否在一个集合中
* @param father
* @param x
* @param y
* @return
*/
public static boolean isSame(int[]father,int x,int y) {
int res1 = findFather(father,x);
int res2 = findFather(father,y);
if(res1==res2)return true;
return false;
}
public static void join(int[]father,int x,int y) {
int res1 = findFather(father,x);
int res2 = findFather(father,y);
if(res1==res2)return ;
father=res1; //把根节点连在一起
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金
页:
[1]