백준 20955번: 민서의 응급 수술(골드 III)
게시글 주소: https://orbi.kr/00061006816
이것도 유니온 파인드를 이용한 기초적인 문제입니다
다만 문제에서 "다음과 같은 연산을 무한히 수행할 수 있다. 연결되지 않은 두 뉴런을 연결하거나 이미 연결된 두 뉴런의 연결을 끊는다." 라는 문장이 있는데, 목표가 모든 뉴런을 하나의 트리로 만드는 것이여서 트리가 아닌(순환 구조가 있을 때) 구조를 만들면 안됩니다.
if(find(u)==find(v)) c++;
이 코드의 의미가 바로 트리를 만들어주는 코드
이미 부모가 같은 상태에서 연결되어 있다는 정보가 추가로 들어오면, 끊는 연산을 수행해서 count를 +1 해줍시다.
#include <stdio.h>
int parent[1000001];
int main()
{
int i,n,m,u,v,c=0;
scanf("%d%d",&n,&m);
for(i=1; i<=n; i++)
parent[i] = i;
for(i=0; i<m; i++)
{
scanf("%d%d",&u,&v);
if(find(u)==find(v)) c++;
merge(u,v);
}
for(i=1; i<n; i++)
{
if(find(i)!=find(i+1))
{
merge(i,i+1);
c++;
}
}
printf("%d",c);
}
int find(int x)
{
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
void merge(int x, int y)
{
x = find(x);
y = find(y);
if (x>y)
parent[y] = x;
else
parent[x] = y;
}
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
좋아요 1 답글 달기 신고
