1707번: 이분 그래프
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수
www.acmicpc.net

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int n,m;
static List[] check;
static int checked[];
//백준 1707번
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t=sc.nextInt();
//테스트 케이스가 0일 될때까지
while(t-->0) {
n= sc.nextInt(); //노드갯수
m= sc.nextInt(); //간선갯수
//배열리스트 쓰는 이유 : 배열을 쓰면 시간초과로 나옴
check =new ArrayList[n+1];
//노드 갯수만큼 리스트에 배열리스트 생성
for(int i=1; i<=n; i++) {
check[i] = new ArrayList();
}
//방문 여부 확인
//0:방문 안함 / 1: 방문한 x소속 / 2:방문한 y소속
checked = new int[n+1];
//좌표 받아서 배열리스트에 집어넣음
for(int k=0; k<m; k++) {
int x=sc.nextInt();
int y=sc.nextInt();
check[x].add(y);
check[y].add(x);
}
for(int i=1; i<=n; i++) {
if(checked[i]==0) { // 정점 i를 방문하지 않은 상태라면
dfs(i, 1);
}
}
if(isPossible()) {
System.out.println("YES");
}else {
System.out.println("NO");
}
}
}
private static boolean isPossible() {
for(int i=1; i<=n; i++) {
for(int k=0; k<check[i].size(); k++) {
if(checked[i]==checked[(int)check[i].get(k)]) {
return false;
}
}
}
return true;
}
private static void dfs(int node, int c) {
checked[node] =c;
for(int i=0; i<check[node].size(); i++) {
int next=(int)check[node].get(i); //지금 선택된 노드에 연결된 노드 값을 가져와서 next에 집어넣음
if(checked[next]==0) { //연결된 노드 값의 checked가 0이면 들리지 않았다는 것 >> 지금 선택된 노드와 연결되었으니 다른 숫자주기 위해서 3-c로 만들어줌
dfs(next,3-c);
}
}
}
}
반응형
'PS > BOJ' 카테고리의 다른 글
| 백준 2750 수 정렬하기 (0) | 2021.07.12 |
|---|---|
| 백준 10451 순열 사이클 JAVA (0) | 2021.04.10 |
| 백준 10814 나이순 정렬 (0) | 2021.04.07 |
| 백준 11651 좌표 정렬하기 2 (0) | 2021.04.07 |
| 백준 11650 좌표 정렬하기 (0) | 2021.04.07 |