[코드그라운드 연습문제] 김씨만 행복한 세상

김씨만 행복한 세상

문제

주어진 그래프로 이분그래프를 만들 수 있는가? 를 판별하는 문제이다.

문제 풀이

주어진 그래프를 입력 받고 임의의 정점에서 다른 정점으로 이동할 때마다 타입을 반전시켜준다.

모순이 발생하면 이분그래프를 만들수 없는 그래프이다.

 

소스 코드

	#include <bits/stdc++.h>
	using namespace std;
	vector<vector<int> > adj;
	int n, m;
	int trip[201];
	//모순이 발생하는 경우 true를 리턴함
	bool dfs(int now, int type){
	trip[now]=type;
	bool ret=false;
	for(int i=0;i<adj[now].size();i++){
	int there=adj[now][i];
	//이미 방문한 정점인데
	if(trip[there]!=-1){
	//현재 정점과 타입이 같다면
	if(trip[there]==type)
	return true;
	continue;
	}
	ret|=dfs(there, 1-type);
	}
	return ret;
	}
	int main(){
	int TestCase;
	scanf("%d", &TestCase);
	for(int tc=1;tc<=TestCase;tc++){
	adj.clear();
	scanf("%d%d", &n, &m);
	adj=vector<vector<int> >(n+1);
	//인접리스트 그래프 입력
	for(int i=0;i<m;i++){
	int a, b;
	scanf("%d%d", &a, &b);
	adj[a].push_back(b);
	adj[b].push_back(a);
	}
	bool ans=false;
	//방문 체크
	memset(trip, -1, sizeof(trip));
	for(int i=1;i<=n;i++){
	//방문하지 않은 모든 정점에 대하여 모순을 계산
	if(trip[i]==-1)
	ans|=dfs(i, 0);
	}
	printf("Case #%d\n%d\n", tc, !ans);
	}
	return 0;
	}

view raw happy.cpp hosted with ❤ by GitHub