BOJ 11724 연결 요소의 개수

출처 : https://www.acmicpc.net/problem/11724

아 먼저 참고할건 이 글은 문제 풀이랑은 상관이 없다.(맨 밑에 정답코드는 넣었다.)

입력을 한번 보자 vn, en이 먼저 주어지고 아래 무방향 엣지 정보인 u v가 주어진다.
여기서 우리는 그래프를 표현해야되는데 가장 짜증 나는건 나는 'C'로 문제를 푼다는 것이다.

Q. 인접행렬로 그래프 표현해 쉽자나
A. 가오떨어지게 그게 뭐임

그래서 인접리스트를 만들어야 하는데

#define max 1000
struct node
{
	int num;
	struct node * next, *pre;
};
struct node *head[max + 1], *tail[max + 1];
int size[max + 1];
void push(int, int);
.
.
.

아 ㅋㅋㅋㅋㅋㅋㅋ 이거 언제 다 치고 있음 ㅋㅋㅋㅋㅋㅋㅋㅋ
(나 연결리스트 짤줄 안다. ㄹㅇ)

그래서 생각한게 'malloc, calloc, realloc 이거 싹다 사용하면 가능하겠다.' 이다.

#include<stdio.h>
#include<malloc.h>
int **elist, *eindex, vn, en;
int answer;
int make_answer();
int main(void)
{
	answer = make_answer();
	printf("%d\n", answer);
	return 0;
}
int make_answer()
{
	int a, b;
	scanf("%d %d", &vn, &en);
	/*
	calloc 하면 0으로 밀어버리니깐
	지금 값을 봤을땐 0 (NULL)이면 할당 안된 상태
	*/
	elist = (int **)calloc(vn + 1, sizeof(int*));
	eindex = (int *)calloc(vn + 1, sizeof(int));
	while (en--)
	{
		scanf("%d %d", &a, &b);
		if (elist[a]) // NULL이 아닌 상태 -> 이미 malloc 한번 했으니깐 이젠 realloc 해야지
		{
			elist[a] = (int *)realloc(elist[a], sizeof(int) * (eindex[a] + 1));
		}
		else // NULL이니깐 처음엔 말록해야지
		{
			elist[a] = (int *)malloc(sizeof(int));
		}
		elist[a][eindex[a]++] = b;
		if (elist[b])
		{
			elist[b] = (int *)realloc(elist[b], sizeof(int) * (eindex[b] + 1));
		}
		else
		{
			elist[b] = (int *)malloc(sizeof(int));
		}
		elist[b][eindex[b]++] = a;
	}
}

malloc, calloc, realloc 뭔지 대충알고 주석 읽어보면 내가 왜 저짓을 해놨는지 이해가 갈것이다.

근데 좀더 찾아보니깐 'realloc의 첫번째 인자가 NULL이면 malloc과 동일하게 동작한다.'
라는걸 찾았음!!!!

이제 이걸사용하면 코드가 절반가량 줄어든다.

#include<stdio.h>
#include<malloc.h>
int **elist, *eindex, vn, en;
int answer;
void pb(int, int);
int make_answer();
int main(void)
{
	answer = make_answer();
	printf("%d\n", answer);
	return 0;
}
int make_answer()
{
	int a, b;
	scanf("%d %d", &vn, &en);
	elist = (int **)calloc(vn + 1, sizeof(int*));
	eindex = (int *)calloc(vn + 1, sizeof(int));
	while (en--)
	{
		scanf("%d %d", &a, &b);
		pb(a, b);
		pb(b, a);
	}
    // 해제
	for (i = 0; i < vn + 1; i++)
	{
		if (elist[i]) // 이거 if문 넣자
		{
			free(elist[i]);
		}
	}
	free(elist);
	free(eindex);
}
void pb(int a, int b)
{
	elist[a] = (int *)realloc(elist[a], sizeof(int) * (eindex[a] + 1));
	elist[a][eindex[a]++] = b;
}

아 이제 우리는 꽤나 간편하게 그래프를 인접리스트로 구현할수 있게 되었다!!!!
사실 이쯤 글 읽는 정상적인 사람이면 'C++ 쓰지 븅신 ㅋㅋㅋ' 이라는 생각을 할것이다.
맞는말이다. 나도 동의 ㅋ

또 궁금한 사람도 있을것이다.
Q. tle 혹은 rte 난적은 없나?
A. 우선 내 수준에서 푸는 문제에 한해서는 전혀없다.

Q. 이거 말고는 다른 방법은 없나??
A. 물론 있다.(한번 해보고 때려치움) u, v쌍을 저장하는 구조체를 정렬한 뒤 하한, 상한 범위내에서 엣지를 보면 된다. 그치만 정렬, 상한, 하한 구현하는 것보다는 이게 훨씬 편하지 않은가?? ;)

bfs 혹은 dfs 혹은 union-find 아래 풀이는 dfs 이다.

#include<stdio.h>
#include<malloc.h>
int **elist, *eindex, vn, en, *memo;
int answer;
void go(int);
void pb(int, int);
int make_answer();
int main(void)
{
	answer = make_answer();
	printf("%d\n", answer);
	return 0;
}
int make_answer()
{
	int i, a, b;
	scanf("%d %d", &vn, &en);
	elist = (int **)calloc(vn + 1, sizeof(int*));
	eindex = (int *)calloc(vn + 1, sizeof(int));
	memo = (int *)calloc(vn + 1, sizeof(int));
	while (en--)
	{
		scanf("%d %d", &a, &b);
		pb(a, b);
		pb(b, a);
	}
	for (i = 1, a = 0; i <= vn; i++)
	{
		if (!memo[i])
		{
			a++;
			memo[i]++;
			go(i);
		}
	}
	// 해제
	for (i = 0; i < vn + 1; i++)
	{
		if (elist[i])
		{
			free(elist[i]);
		}
	}
	free(elist);
	free(eindex);
	free(memo);
	return a;
}
void pb(int a, int b)
{
	elist[a] = (int *)realloc(elist[a], sizeof(int) * (eindex[a] + 1));
	elist[a][eindex[a]++] = b;
}
void go(int cur)
{
	int d, next;
	for (d = 0; d < eindex[cur]; d++)
	{
		next = elist[cur][d];
		if (!memo[next])
		{
			memo[next]++;
			go(next);
		}
	}
}