#83. [백준_C언어] 1707 : 이분 그래프 \ 그래프 탐색

 

입력 코드

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int K;
int V, E;
int stop;
int cnt;

int** graph;
int* count;
int* group;
int* check;

int* N1;
int* N2;

void Dfs(int num, int group_);

int main()
{
	int k;
	int v, e;
	int n1, n2;

	scanf("%d", &K);

	for (k = 1; k <= K; k++)
	{
		scanf("%d %d", &V, &E);

		graph = (int**)calloc(V + 1, sizeof(int*));
		count = (int*)calloc(V + 1, sizeof(int));
		check = (int*)calloc(V + 1, sizeof(int));
		group = (int*)calloc(V + 1, sizeof(int));
		N1 = (int*)calloc(E + 1, sizeof(int));
		N2 = (int*)calloc(E + 1, sizeof(int));

		for (e = 1; e <= E; e++)
		{
			scanf("%d %d", &n1, &n2);
			count[n1]++;
			count[n2]++;
			N1[e] = n1;
			N2[e] = n2;
		}

		for (v = 1; v <= V; v++)
		{
			graph[v] = (int*)calloc(count[v] + 1, sizeof(int));
			count[v] = 0;
		}

		for (e = 1; e <= E; e++)
		{
			graph[N1[e]][++count[N1[e]]] = N2[e];
			graph[N2[e]][++count[N2[e]]] = N1[e];
		}

		for (v = 1; v <= V; v++)
		{
			if (check[v] == 1)	continue;
			check[v] = 1;
			Dfs(v, 1);
		}

		if (stop == 0)	printf("YES\n");
		if (stop == 1)	printf("NO\n");

		free(graph);
		free(count);
		free(check);
		free(group);
		free(N1);
		free(N2);

		stop = 0;
		cnt = 0;	
	}
}

void Dfs(int num, int group_)
{
	int n, m;
	int v;

	for (n = 1; n <= count[num]; n++)
	{
		m = graph[num][n];

		if (group[m] == group_)
		{
			stop = 1;
			return;
		}

		else
		{
			if (check[m] == 0)
			{
				group[m] = group_ * (-1);
				check[m] = 1;
				Dfs(m, group_ * (-1));

				if (stop == 1)	return;
			}
		}
	}
}

 

출처 www.acmicpc.net/source/19236799

 

 

코드 설명

#그래프이론 #그래프탐색 #너비우선탐색

 

 

 

문제 출처

www.acmicpc.net/problem/1707

1707번: 이분 그래프