글 읽기 - 이분그래프 찾기 질문이에요

cocobo123 6년 전 0

처음에 저 아이디어로 해봤는데

연결요소가 2개이상인거는 이분그래프가 아닌거를 생각못해서

그 알고리즘을 추가했거든요??

그런데 틀렸다고 나옵니다.

어느부분을 생각하지 못한걸까요????

#include<stdio.h>

int K, V, E;
int g[2][20002];
int s[20002];
int find(int x)
{
	return x == s[x] ? x : (s[x] = find(s[x]));
}

int unionSet(int x1, int x2)
{
	x1 = find(x1);
	x2 = find(x2);
	int min = x1 > x2 ? x2 : x1;
	s[x1] = s[x2] = min;
	return x1 != x2;
}
int main()
{
	scanf("%d", &K);
	
	while (K--)
	{
		int SetA=0, SetB=0, cnt;
		scanf("%d %d",&V, &E);
		for (int i = 0; i <= V; i++)
		{
			g[0][i] = g[1][i] = 0;
			s[i] = i;
		}
		cnt = V;
		while (E--)
		{
			int f, t;
			scanf("%d %d", &f, &t);
			cnt -= unionSet(f, t);
			if (f == 1)
				g[1][t] = 1;
			if (t == 1)
				g[1][f] = 1;
			g[0][f]++;
			g[0][t]++;
		}
		if (cnt == 1)
		{
			for (int i = 1; i <= V; i++)
			{
				if (g[1][i] == 1)
					SetA += g[0][i];
				else
					SetB += g[0][i];
			}
			printf("%s\n", SetA == SetB ? "YES" : "NO");
			
		}
		else
			printf("NO\n");
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이분그래프 찾기 질문이에요

cocobo123 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말