207. 课程表
//思路：
//实际上是一个有向图问题：
//该图是一个有向无环图，则可能完成所有课程的学习
//该图中存在环，则不可能完成所有课程的学习
//这里不需要使用拓扑排序，只需要检测有向图是否存在环即可。
private ArrayList<Integer> [] g; //表示该有向无环图
private boolean[] visited; //记录访问过的顶点
private boolean[] onPath; //记录是否为有向环的顶点
public boolean canFinish(int numCourses, int[][] prerequisites) {
//构建该有向无环图，注意要对每个元素进行初始化
g = new ArrayList[numCourses];
for(int i=0;i<numCourses;i++){
g[i] = new ArrayList<>();
}
for(int[] prerequisity : prerequisites){
//注意：[1,0] 表示先学习课程 0 ，再学习课程 1
//转化为图后，可这样表示 0 --> 1
int from = prerequisity[1];
int to = prerequisity[0];
g[from].add(to);
}
return !hasCycle();
}
//判断该图是否存在环
//存在环则返回 true
private boolean hasCycle(){
visited = new boolean[g.length];
onPath = new boolean[g.length];
for(int i=0;i<g.length;i++){ //遍历图的所有顶点
if(!visited[i]){
if(dfs(i)){
return true;
}
}
}
return false;
}
//从顶点 v 开始，进行深度遍历
//如果存在环，则返回 true
private boolean dfs(int v){
visited[v] = true;
onPath[v] = true; //这里假设 v 是环的顶点
for(int adj : g[v]){ // v 顶点所有相邻的顶点
if(!visited[adj]){
if(dfs(adj)){ //从 adj 开始，进行深度遍历，存在环
return true;
}
}else if(onPath[adj]){ //相邻的点在环上,说明存在环
return true;
}
}
//前面循环正常结束，说明以 v 为起点不存在环
onPath[v] = false; //TODO:此次深度遍历，v 不在环上
return false;
}
@Test
public void test(){
int numCourses =2;
int[][] prerequisites = {{1,0}};
//int[][] prerequisites = {{1,0},{0,1}};
System.out.println(canFinish(numCourses,prerequisites));
}//思路：上一题 207 的变形
//先判断是否存在环，如果存在环,则返回 []
//如果不存在环，则求出拓扑顺序
private boolean[] visited;
private boolean[] onPath; //记录在环上的节点
Stack<Integer> stack;//存储拓扑顺序的逆序序列
//为什么会使用 stack?
//因为 dfs 的特性:比如 1->3 dfs会访问3，stack.push(3),然后访问1，stack.push(1)。
public int[] findOrder(int numCourses, int[][] prerequisites) {
ArrayList<Integer>[] g = new ArrayList[numCourses];
for(int i=0;i<numCourses;i++){
g[i]=new ArrayList<>();
}
for(int[] prerequisit:prerequisites){
int from = prerequisit[1];
int to = prerequisit[0];
g[from].add(to);
}
visited=new boolean[numCourses];
onPath=new boolean[numCourses];
stack = new Stack<>();
//先判断 g 是否有环
if(hasCycle(g)){
return new int[]{};
}
int[] res = new int[stack.size()];
int index=0;
while (!stack.isEmpty()){
res[index++] = stack.pop();
}
return res;
}
//判断 g 是否有环
//如果存在环则返回 true
private boolean hasCycle(ArrayList<Integer>[] g){
for(int i=0;i<g.length;i++){
if(!visited[i]){
if(dfs(g,i)){
return true;
}
}
}
return false;
}
//从顶点 v 开始，进行深度遍历
//如果存在环，则返回 true
private boolean dfs(ArrayList<Integer>[] g,int v){
visited[v]=true;
onPath[v]=true;
for(int adj:g[v]){
if(!visited[adj]){
if(dfs(g,adj)){
return true;
}
}else if(onPath[adj]){
return true;
}
}
onPath[v]=false;
stack.push(v);
return false;
}
@Test
public void test(){
int numCourses=2;
int[][] prerequisites={
{1,0}
};
// int[][] prerequisites={
// {1,0},
// {2,0},
// {3,1},
// {3,2}
// };
int[] res = findOrder(numCourses,prerequisites);
for(int num:res){
System.out.println(num);
}
}785. 判断二分图
//思路：典型的二分图思路
//如果该图可以用两种颜色对图中的节点进行着色，并且保证相邻的顶点颜色不同，
//那么这个图就是二分图。
private int[] color;
// color[i] 中的 i 表示顶点 i 元素
// 若 color[i] = -1，则表示 i 元素尚未被涂色
// 若 color[i] = 0，则表示 i 元素被涂为 0 色
// 若 color[i] = 1，则表示 i 元素被涂为 1 色
public boolean isBipartite(int[][] graph) {
color = new int[graph.length];
//开始时，所有的顶点，都没上色
Arrays.fill(color,-1);
for(int i=0;i<graph.length;i++){
if(color[i]==-1){ //先判断顶点 i 是否已经被涂色
if(!paint(graph,i,0)){
//存在顶点涂色失败的，则不可能是二分图
return false;
}
}
}
return true;
}
//从顶点 index 开始对该图进行涂色，涂的颜色是 group
//注意： group 的取值是 0 或者 1，所以当group=0时,1-group=1就表示另外一种颜色;
private boolean paint(int[][] graph,int index,int group){
if(color[index]!=-1){ // index 已经被涂色
return color[index] == group; //顶点 index 是否被涂成 group 颜色
}
color[index] = group; //为顶点 index 涂上 group 色
for(int adj:graph[index]){ // index 相邻的顶点不能和 index 涂成相同颜色
if(!paint(graph,adj,1-group)){
//index 相邻的顶点中存和 index 涂成相同的元素的顶点，则涂色失败
return false;
}
}
return true;
}
@Test
public void test(){
// int[][] graph = {
// {1,3},
// {0,2},
// {1,3},
// {0,2}
// };
int[][] graph = {
{1,2,3},
{0,2},
{0,1,3},
{0,2}
};
System.out.println(isBipartite(graph));
}886. 可能的二分法
//思路：根据 we would like to split everyone into two groups of any size.
//马上想到二分图。
//这里要注意图的表示
private int[] color;
// color[i] 中的 i 表示顶点 i 元素
// 若 color[i] = -1，则表示 i 元素尚未被涂色
// 若 color[i] = 0，则表示 i 元素被涂为 0 色
// 若 color[i] = 1，则表示 i 元素被涂为 1 色
public boolean possibleBipartition(int N, int[][] dislikes) {
//将该问题转化为一个二分图问题
HashSet<Integer>[] g = new HashSet[N];
for(int i=0;i<N;i++){
g[i] = new HashSet<>();
}
for(int[] dislike:dislikes){
//注意：这里人的编号是从1开始的，为了后续使用数组处理方便，全部做减 1 处理
int from = dislike[0]-1;
int to = dislike[1]-1;
g[from].add(to);
g[to].add(from);
}
color = new int[N];
Arrays.fill(color,-1);
for(int i=0;i<N;i++){
if(color[i]==-1){
if(!paint(g,i,0)){
return false;
}
}
}
return true;
}
//从顶点 index 开始对该图进行涂色，涂的颜色是 group
//注意： group 的取值是 0 或者 1，所以当group=0时,1-group=1就表示另外一种颜色
private boolean paint(HashSet<Integer>[] g,int index,int group){
if(color[index]!=-1){
return (color[index] == group);
}
color[index] =group;
for(Integer adj:g[index]){
if(!paint(g,adj,1-group)){
return false;
}
}
return true;
}
@Test
public void test(){
// int N = 4;
// int[][] dislikes = {
// {1,2},
// {1,3},
// {2,4}
// };
// int N = 3;
// int[][] dislikes = {
// {1,2},
// {1,3},
// {2,3}
// };
int N = 5;
int[][] dislikes = {
{1,2},
{2,3},
{3,4},
{4,5},
{1,5}
};
System.out.println(possibleBipartition(N,dislikes));
}