백준 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 답글 달기 신고
-
집에 가야겠다 0
왜 독서실에 에어컨을 안틀어놓는거야
-
술이나 먹자 6
안주를 사오자
-
a^n+2^n+1|a^(n+1)+2^(n+1)+1 자연수 a,n
-
자연수...
-
(4x-y)(4y-x)=30^6. x,y자연수(x,y)의 개수는?
-
풍경이 아름답죠? 가는 길 외롭지 않게 응원해주세요. 하 집까지 겁나 머네 진짜
-
x^4-2y^2=1x,y 정수해 2개
-
무덤 속의 벙어리를 말한 셈이다
-
sqrt(x)+sqrt(y)=sqrt(z)자연수, x,y,z 해 무한개임
-
일단 정년 연장하는데 청년 일자리가 어떻게 늘어나냐 하니까 너무 극단적이라고...
-
보통어느정도 푸시나용
-
[자료] 공통+확/미/기 전범위 수학 실모 하나 뿌림 6
예에엣날에 만든 문제들 짜깊기해서 만든 문제라서 요즘 트랜드에 맞지 않을 가능성이...
-
부정방정식 풀어보실 15
m^n=n^(m-n)m,n은 자연수
-
x!+y!=x^yx,y는 자연수
-
심심함
-
n*2^(n+1)+1=k^2.n,k 는 자연수
-
지방러라 울었다 9
서울 근처 안살아서 서울 한 번 가는데만 시간과 돈이 얼마나 깨지는거야 고생은 덤이고 에휴
-
축하해드림
-
차단률이 감소한다고한다 --
-
자야지
-
필기 안해봄 4
도전해봣는데 끔찍해서 관둠
-
ㅈ같다 벌써
-
왜 다 어디서 본 문제들이지
-
제 선택과목 3
물화생지
-
국어를 잘해져서 1
훈수두고 싶다
-
폰이 너무너무 무거워짐
-
진도율 5퍼 7
사실 한 3번 들어서 305퍼임
-
본인 37점인데 백분위 90 2등급뜸
-
어라?
-
자고 싶다 0
영~원히
-
정시 관련 질문 3
정시 생각중인 고2인데요ㅠㅠ 아는게 없어서 질문 많이 달아요 아는거 아무거나...
-
난 다 들었는데 0
진도율 보정을 어케했길래 이지랄 남 다른 강의들도 진도가 반토막남
-
어디든 좋으니 나와 가줄래
-
국어 문학은 수특 문제 풀고 ebs 인강 듣고 있고 비문학은 혼자 글을 이해하는게...
-
학습은 뇌가 알아서 해주겟지 해줘 그냥
-
3단원 끝남 6
사실 끝낫다는게 개념만 쭉 들엇음 사실 그마저도 1강 남앗음 4단원 강의 개 많음 종합적으로 귀찮
-
오노추 2
-
고등학교만 10년 다닐뻔함 수업 몇시수 들었는지 체크해서 시수 모자르면 미이수 된다던데
-
일단 수학은 원래 수1 수2 알텍 3회독 하면서 기출 2회독 정도하고 미적은 생질,...
-
회차별로 0~2개정도 틀리는것같은데 이제 뭐해야할까요? 사규는 이미 배송시킴
-
6모 생명은 6
샤가프랑 복제추론, 코돈, 뭐지?이렇게 4개인가 근데 개념형도 못 풀꺼 같은데 음..
-
생각하지 못한 반전과 친구들과 일탈과 누려보지 못한 성인+자유는 극락이라고 생각함...
-
서울갓반 과중고 2점대인데 이 점수로 목표대학은 어려울 거 같아 정시 파이터가...
-
-
너와 마신 커피 한 잔에도 난 세상을 가졌어
-
일어나보니 4
너가 없더라
-
뭐 왓츄세이
-
송도가 유배지면 2
여긴 뭘까
-
오르비 잘자 6
-
만약에 간다고 하면 사문이 낫나요 아니면 생윤이 낫나요?
