이분 도 판단 (염색, DFS)
graph， true。
A B， A ， B ， 。
graph ，graph[i] i 。 0 graph.length-1 。 ： graph[i] i， graph[i] 。
1:
: [[1,3], [0,2], [1,3], [0,2]]
: true
:
:
0----1
| |
| |
3----2
: {0, 2} {1, 3}。
2:
: [[1,2,3], [0,2], [0,1,3], [0,2]]
: false
:
:
0----1
| \ |
| \ |
3----2
。
:
graph [1, 100]。
graph[i] [0, graph.length - 1]。
graph[i] i 。
: j graph[i] , i graph[j] 。
코드
class Solution {
// ， ： 、
private static final int UNCOLORED = 0;
private static final int RED = 1;
private static final int GREEN = 2;
//
private int[] color;
//
private boolean valid = true;
public boolean isBipartite(int[][] graph) {
//
int n = graph.length;
color = new int[n];
for (int i = 0; i < n; i++) {
// ，
if (color[i] == UNCOLORED) {
dfs(i, RED, graph);
}
}
return valid;
}
private void dfs(int node, int c, int[][] graph) {
color[node] = c;
//
int nc = c == RED ? GREEN : RED;
//
for (int neighbor : graph[node]) {
// ，
if (color[neighbor] == UNCOLORED) {
dfs(neighbor, nc, graph);
//
if (!valid) {
return;
}
// ， ，
} else if (color[neighbor] != nc) {
valid = false;
return;
}
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
string 헤더 사용해보기(8958)CPP에서는 char 포인터로 문자열을 받는 것 이외에 string 헤더를 통하여 문자열을 배열 형태로 저장할 수 있다 결과: str[0] = f str[1] = i str[2] = r str[3] = s str[4...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
