Weekly Contest 72 leetcode 785. Is Graph Bipartite?

3781 ワード
lettecode
Given a  graph , return  true  if and only if it is bipartite.
Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form:  graph[i]  is a list of indexes  j  for which the edge between nodes  i  and  j  exists.  Each node is an integer between  0  and  graph.length - 1 .  There are no self edges or parallel edges:  graph[i]  does not contain  i , and it doesn't contain any element twice. 
Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.

Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent ubsets.

 
Note:
  • graph  will have length in range  [1, 100] .
  • graph[i]  will contain integers in range  [0, graph.length - 1] .
  • graph[i]  will not contain  i  or duplicate values.

    • この問題は実は簡単だ.ここのbipartiteは辞書の定義ではなく、ここの定義であることに注意してください.
    すなわち、すべての点を2つのsetに入れ、1つの辺の2つの点m,nを保証し、m点が集合Aにある場合、n点は集合Bにあるべきである.
    私の考えは、iとgraph[i][j]を出して、i点が集合Aなのか集合Bなのかを判断することです.前にi点をセットAに入れた場合はbelongTo=1を設定します.前にgraph[i][j]のいずれかの点を集合Aに入れた場合、i点は集合Bに入れ、belongTo=2を設定すべきである.belongTo=-1、すなわち、これまでi点とすべてのgraph[i][j]点が入っていなかった場合、私たちは勝手に置くことができるので、iを集合Aに入れ、すべてのgraph[i][j]を集合Bに入れるとよい.△これらの点に遭遇したことがないので、前の結果には影響しません.その後の点は、これらの点との関係を判断し、対応する集合を加えます.
    package leetcode;

import java.util.HashSet;
import java.util.Set;

public class Is_Graph_Bipartite_785 {

	public boolean isBipartite(int[][] graph) {
		Set setA = new HashSet<>();
		Set setB = new HashSet<>();
		for (int i = 0; i < graph.length; i++) {
			int belongTo = -1; //    i  belongTo    
			if (setA.contains(i)) {
				belongTo = 1;
			}
			for (int j = 0; j < graph[i].length; j++) {
				if (setA.contains(graph[i][j])) {
					belongTo = 2;
					break;
				}
			}
			if (belongTo == -1) {//   set         ，  belongTo        
				setA.add(i);
				for (int j = 0; j < graph[i].length; j++) {
					setB.add(graph[i][j]);
				}
			} else if (belongTo == 1) {
				for (int j = 0; j < graph[i].length; j++) {
					if (setA.contains(graph[i][j])) {
						return false;
					} else {
						setB.add(graph[i][j]);//      ，  ，      
					}
				}
			} else {// belongTo==2
				setB.add(i);
				for (int j = 0; j < graph[i].length; j++) {
					if (setB.contains(graph[i][j])) {
						return false;
					} else {
						setA.add(graph[i][j]);//      ，  ，      
					}
				}
			}
		}
		return true;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Is_Graph_Bipartite_785 is=new Is_Graph_Bipartite_785();
		int[][] graph=new int[][]{
			{1,2,3},{0,2},{0,1,3},{0,2}
		};
		System.out.println(is.isBipartite(graph));
	}
}

    私のブログに書いた時間は、大神のdiscussが出ていませんでした.だからこれを先に置いて、後で大神がアップロードしたdiscussを見ます.https://leetcode.com/problems/is-graph-bipartite/discuss/
    JAvaで各単語のアルファベットをどのように反転させるかは、「To be or not to be」を「oT eb roton ot eb」に変えることです
    Netstat使用の詳細