二分图算法
import java.util.Scanner;public class Main
{public static int n_vertex;public static int n_edges;public static int[][] adjMatrix;public static int[] color;public static boolean dfs(int v,int c){color[v]=c;for(int i=1;i<=n_vertex;i++){if(adjMatrix[v][i]==1){if(color[i]==c)return false;if(color[i]==0 && !dfs(i,-c))return false;}}return true;}public static String solve(){for(int i=1;i<=n_vertex;i++){if(color[i]==0){if(!dfs(i,1)){return "No";}}}return "Yes";}public static void main(String[] args){Scanner in = new Scanner(System.in);n_vertex=in.nextInt();n_edges=in.nextInt();color=new int[n_vertex+1];adjMatrix=new int[n_vertex+1][n_vertex+1];for(int i=0;i<n_edges;i++){int start=in.nextInt();int end=in.nextInt();adjMatrix[start][end]=1;adjMatrix[end][start]=1;}System.out.println(solve());}
}
207. Course Schedule
图的拓扑排序
算法一：dfs
class Solution {public static int[] visitStatus;public static ArrayList<ArrayList<Integer>> adjList;public boolean canFinish(int numCourses, int[][] prerequisites) {adjList=new ArrayList<>();visitStatus=new int[numCourses];for(int i=0;i<numCourses;i++)adjList.add(new ArrayList<>());for(int[] tmp:prerequisites){adjList.get(tmp[1]).add(tmp[0]);}for(int i=0;i<numCourses;i++){if(visitStatus[i]!=0)continue;if(!dfs(i))return false;}return true;}public static boolean dfs(int i){visitStatus[i]=1;for(int j=0;j<adjList.get(i).size();j++){int m=adjList.get(i).get(j);if(visitStatus[m]==2)continue;if(visitStatus[m]==1)return false;if(!dfs(m))return false;}visitStatus[i]=2;return true;}
}
算法二：Kahn’s algorithm
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int[] indegrees=new int[numCourses];ArrayList<ArrayList<Integer>> adj=new ArrayList<>();for(int i=0;i<numCourses;i++)adj.add(new ArrayList<>()); for(int[] tmp:prerequisites) //邻接表构建{adj.get(tmp[1]).add(tmp[0]);indegrees[tmp[0]]++;}Queue<Integer> q=new LinkedList<>();for(int i=0;i<numCourses;i++){if(indegrees[i]==0)q.add(i);}int cnt=0;ArrayList<Integer> ans=new ArrayList<>();while(!q.isEmpty()){int tmp=q.poll();ans.add(tmp);for(int i:adj.get(tmp)){if(--indegrees[i]==0)q.add(i);}cnt++;}return cnt==numCourses;}
}
210. Course Schedule II
算法一：dfs
class Solution {public static int[] reversePost;public static int idx;public static int[] visitStatus;public static ArrayList<ArrayList<Integer>> adjList;//邻接表public int[] findOrder(int numCourses, int[][] prerequisites) {idx=numCourses-1;reversePost=new int[numCourses];adjList=new ArrayList<>();visitStatus=new int[numCourses];for(int i=0;i<numCourses;i++)adjList.add(new ArrayList<>());for(int[] tmp:prerequisites){adjList.get(tmp[1]).add(tmp[0]);}for(int i=0;i<numCourses;i++){if(visitStatus[i]!=0)continue;if(!dfs(i))return new int[0];}return reversePost;}public static boolean dfs(int i){visitStatus[i]=1;for(int j=0;j<adjList.get(i).size();j++){int m=adjList.get(i).get(j);if(visitStatus[m]==2)continue;if(visitStatus[m]==1)return false;if(!dfs(m))return false;}visitStatus[i]=2;reversePost[idx--]=i;return true;}}
算法二：
class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {int[] indegrees=new int[numCourses];ArrayList<ArrayList<Integer>> adj=new ArrayList<>();for(int i=0;i<numCourses;i++)adj.add(new ArrayList<>()); for(int[] tmp:prerequisites) //邻接表构建{adj.get(tmp[1]).add(tmp[0]);indegrees[tmp[0]]++;}Queue<Integer> q=new LinkedList<>();for(int i=0;i<numCourses;i++){if(indegrees[i]==0)q.add(i);}int cnt=0;int[] ans=new int[numCourses];while(!q.isEmpty()){int tmp=q.poll();ans[cnt]=tmp;;for(int i:adj.get(tmp)){if(--indegrees[i]==0)q.add(i);}cnt++;}return cnt==numCourses?ans:new int[0];}
}
1136. Parallel Courses
实际上也是在做拓扑排序
class Solution {public int minimumSemesters(int N, int[][] relations) {ArrayList<ArrayList<Integer>> adj=new ArrayList<>();int[] indegrees=new int[N];for(int i=0;i<N;i++)adj.add(new ArrayList<>()); for(int[] tmp:relations) //邻接表构建{adj.get(tmp[0]-1).add(tmp[1]-1);indegrees[tmp[1]-1]++;}Queue<Integer> q=new LinkedList<>();for(int i=0;i<N;i++){if(indegrees[i]==0)q.add(i);}int ans=0;while(!q.isEmpty()){int n=q.size();for(int i=0;i<n;i++){int tmp=q.poll();N--;for(int v:adj.get(tmp)){if(--indegrees[v]==0){q.add(v);}}}ans++;}return N==0?ans:-1;}
}