1707번: 이분 그래프

문제 설명

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

[문제]

 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

 

[입력]

 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

 

[출력]

 K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

 

[예제 입력 1]

2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2

[예제 출력 1]

YES
NO

---

풀이

 이분 그래프를 이루기 위해선 연결 노드끼리는 서로 다른 팀에 있어야 하기에, DFS를 통해 연결된 노드를 끝까지 탐색하여 팀들을 정할 수 있어야 한다. 그래서 팀을 -1, 1로 정하고 이들을 서로 다른 팀을 지정할 때 -1을 곱하는 것으로 하여, 현재 위치의 팀이 정해져있기만 하면 해당 값을 몰라도 연결된 노드의 팀을 저장할 수 있게 했다.

 추가적으로 팀을 정하는 DFS 과정을 모두 거치고 다시 연결 노드를 바탕으로 팀이 어긋나는 곳을 찾을 수도 있지만, 나름대로 시간과 공간을 절약해보고자 DFS 과정 속에서 비교 조건을 넣어, 이미 저장되어 있는 팀과 현재 계산된 팀이 다른 경우 탐색을 바로 끝내고 정답을 도출할 수 있도록 했다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int nodeinfor[20001];

void check(int node, int team, vector<vector<int>>& graph, bool& result) {//DFS 기반
	nodeinfor[node] = team;

	for (int i = 0; i < graph[node].size(); i++) {
		int next = graph[node][i];
		if (nodeinfor[next] == 0) //연결 노드의 팀이 정해지지 않은 경우
			check(next, team * -1, graph, result);
		else
			if (team == nodeinfor[next]) {//이미 팀이 정해져있는데 계산과 다른 경우
				result = false;
				return;
			}
	}
}

int main() {
	int K, V, E;
	vector<string> answer;
	cin >> K;

	for (int i = 0; i < K; i++) {//케이스 마다		
		int node1, node2;
		bool result = true;
		vector<vector<int>> graph;
		cin >> V >> E;

		memset(nodeinfor, 0, sizeof(nodeinfor));

		for (int j = 0; j <= V; j++) {//정점 연결리스트 초기화
			vector<int> temp;
			graph.push_back(temp);
		}

		for (int j = 0; j < E; j++) {//노드 연결 저장
			cin >> node1 >> node2;
			graph[node1].push_back(node2);
			graph[node2].push_back(node1);
		}

		for (int j = 1; j <= V && result; j++)//노드 탐색
			if (nodeinfor[j] == 0)
				check(j, 1, graph, result);
		
		if (result) //결과에 따라
			answer.push_back("YES");
		else
			answer.push_back("NO");
	}
	
	for (int i = 0; i < K; i++)
		cout << answer[i] << endl;
	
	return 0;
}

---

결과