1.bfs
package QiNiuYun; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main2 { private static boolean isconnect(int N,int[][] tu){ boolean ansflag = true; boolean[] isused = new boolean[N]; List<Integer> jxlist = new ArrayList<>();//。队列 isused[0] = true;//。首先选择一个开始节点,染成黑色(表示访问过) jxlist.add(0);//。将开始节点放入队列 while (!jxlist.isEmpty()){ int jx = jxlist.get(0);//。从队列首部选出一个顶点 jxlist.remove(0);//。该选出的顶点从队头出队 //。访问所有与该顶点邻接的点,访问后将该些邻接点染成黑色并按顺序入依次入队 for (int i =0;i<N;i++){ if (!isused[i] && tu[jx][i]!=0){ isused[i] = true; jxlist.add(i); } } } for (int i=0;i<N;i++){ if (!isused[i]) ansflag = false; } return ansflag; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[][] tu = new int[N][N]; for (int i=0;i<M;i++){ int u = sc.nextInt(),v = sc.nextInt(); tu[u-1][v-1] = 1; tu[v-1][u-1] = 1; } if (isconnect(N,tu)){ System.out.println("YES"); }else { System.out.println("NO"); } sc.close(); } }
2.dfs_rec+dfs_stack
package QiNiuYun; import java.util.Scanner; import java.util.Stack; public class Main3 { private static void dfs_rec(int start,boolean[] visited,int N,int[][] tu){ visited[start] = true; for (int i =0;i<N;i++){ if (!visited[i] && tu[start][i]!=0) dfs_rec(i,visited,N,tu); } } private static void dfs_stack(boolean[] visited,int N,int[][] tu){ Stack<Integer> stack = new Stack<>(); stack.add(0); visited[0] = true; while (!stack.isEmpty()){ boolean ispushed = false; int tmp = stack.peek(); for (int i =0;i<N;i++){ if (!visited[i] && tu[tmp][i]!=0){ visited[i] = true; stack.add(i); ispushed = true; break; } } if (!ispushed) stack.pop(); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); boolean ans = true; int N = sc.nextInt(),M = sc.nextInt(); int[][] tu = new int[N][N]; boolean[] visited = new boolean[N]; for (int i =0;i<M;i++){ int u = sc.nextInt(), v = sc.nextInt(); tu[u-1][v-1] = 1; tu[v-1][u-1] = 1; } for (int i =0;i<N;i++){ if (visited[i]) continue; dfs_rec(0,visited,N,tu); } for (boolean x:visited){ if (!x) { ans = false; break; } } if (!ans) System.out.println("NO"); else System.out.println("YES"); } }
3.判断欧拉回路(度为偶数;昨晚看错题目了,以为是欧拉回路,调了半天只过55.56%,今早起来仔细一想,题意只要判断连通。。。。)
package QiNiuYun; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { private static boolean isconnect(int N,int[][] tu){ boolean ansflag = true; boolean[] isused = new boolean[N]; List<Integer> jxlist = new ArrayList<>(); isused[0] = true; jxlist.add(0); while (!jxlist.isEmpty()){ int jx = jxlist.get(0); jxlist.remove(0); for (int i =0;i<N;i++){ if (!isused[i] && tu[jx][i]!=0){ isused[i] = true; jxlist.add(i); } } } for (int i=0;i<N;i++){ if (!isused[i]) ansflag = false; } return ansflag; } private static boolean iseven(int[] du){ boolean ansflag = true; for (int i =0;i<du.length;i++){ if (du[i]%2!=0){ ansflag = false; } } return ansflag; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[][] tu = new int[N][N]; int[] du = new int[N]; for (int i=0;i<M;i++){ int u = sc.nextInt(),v = sc.nextInt(); tu[u-1][v-1] = 1; tu[v-1][u-1] = 1; du[u-1]++; du[v-1]++; } if (isconnect(N,tu) && iseven(du)){ System.out.println("YES"); }else { System.out.println("NO"); } sc.close(); } }
4.并查集 正在学习中
全部评论
(0) 回帖