Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- abstract
- 바이트코드
- HeapArea
- MethodArea
- SRP
- 포함관계
- la-piscine
- 상속관계
- LSP
- RDD
- Operating System
- JVM
- 도커네트워크
- JIT
- 42seoul
- 이노베이션아카데미
- 라피신
- 42서울
- javac
- StackArea
- 참조변수
- 자바컴파일러
- java
- 운영체제
- classloader
- 제네릭스
- jdk
- generics
- Compiler
- pg_hba.conf
Archives
- Today
- Total
while(1) 작심삼일();
[백준 1707번] 이분 그래프 본문
http://www.acmicpc.net/problem/1707
1707번: 이분 그래프
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수
www.acmicpc.net
풀이)
bfs를 통해 방문하지 않은 곳을 전부 색칠한다. 여기서 나와 연결되어 있는 정점들은 계속 반대의 색상을 넣어준다. 전부를 돌면서 다 색상을 칠한 뒤 이분그래프의 개념과 동일하게 다 맞게 칠해졌는지 확인한다.
참고 : ko.wikipedia.org/wiki/이분_그래프
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
int K, V, E, a, b;
vector<int> graph[20001];
int visited[20001];
void bfs(int start)
{
queue<int> q;
visited[start] = 1;
q.push(start);
while (!q.empty())
{
int now = q.front();
q.pop();
for (int i = 0; i < graph[now].size(); i++)
{
int next = graph[now][i];
if (visited[next] == -1)
{
visited[next] = visited[now] ? 0 : 1;
q.push(next);
}
}
}
}
int isBipartiteGraph()
{
for (int i = 1; i <= V; i++)
{
for (int j = 0; j < graph[i].size(); j++)
{
int next = graph[i][j];
if (visited[i] == visited[next])
return (0);
}
}
return (1);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> K;
while (K--)
{
for (int i = 1; i <= V; i++)
graph[i].clear();
memset(visited, -1, sizeof(visited));
cin >> V >> E;
while (E--)
{
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
for (int i = 1; i <= V; i++)
if (visited[i] == -1)
bfs(i);
if (isBipartiteGraph())
cout << "YES\n";
else
cout << "NO\n";
}
return (0);
}
제 코드는 절대 완벽하지 않습니다
더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!
'CS > baekjoon' 카테고리의 다른 글
[백준 9466번] 텀 프로젝트 (0) | 2021.04.04 |
---|---|
[백준 1744번] 수 묶기 (0) | 2021.04.03 |
[백준 2056번] 작업 (0) | 2021.04.03 |
[백준 1197번] 최소 스패닝 트리 (0) | 2021.04.02 |
[백준 15683번] 감시 (0) | 2021.04.02 |
Comments