무브

오르비

아톰

내 태그

내 태그 설정

입시
학습
생활
클럽
직업·취업
Epioptimus
Centurion

수능쎈츄 [1174003] · MS 2022 · 쪽지

2023-01-02 14:14:20
조회수 2,001

백준 20955번: 민서의 응급 수술(골드 III)

게시글 주소: https://orbi.kr/00061006816

https://orbi.kr/00060992012

이것도 유니온 파인드를 이용한 기초적인 문제입니다

다만 문제에서 "다음과 같은 연산을 무한히 수행할 수 있다. 연결되지 않은 두 뉴런을 연결하거나 이미 연결된 두 뉴런의 연결을 끊는다." 라는 문장이 있는데, 목표가 모든 뉴런을 하나의 트리로 만드는 것이여서 트리가 아닌(순환 구조가 있을 때) 구조를 만들면 안됩니다. 


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)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

수능쎈츄 [1174003]

쪽지 보내기

글쓰기
오르비 1381583번째 회원 가입
ddna
1,422,072 건의 게시물이
블록체인에 디지털 공증되었습니다.
901,751
497,321
22,267
574
159

오르비 캐스트

2026 수능D - 264

오르비 플레이
오르비 RARE
오르비 과외시장
Move
our corporate site
Orbi Class
on-line classes
Atom
educational books & resources
Gae9
humor and fun

© 2000-2025 Move Inc.

orbisoptimus (v17-704e1f)