[백준 9938] 방 청소

https://www.acmicpc.net/problem/9938

9938번: 방 청소

1/6일날 풀었던 문제

요구사항

1. 빈 서랍에 술을 저장할 수 있나 없나에 대해 답을 하는 문제

 

풀이

1. 주어지는 입력을 통로라고 생각하고 하나로 쭉 이어준다

2. 적합한 자료구조인 Union-Find 사용한다.

 

#include <stdio.h>
#include <algorithm>
#include <list>
#include <iostream>

using namespace std;
 
struct NODE {
    int prev;
    int next;
    int val;
};
const int PN=23;
const int SIZE=100000;
int table[100001];
bool visit[300001];
int parent[300001];
int Find(int x)
{
    if(parent[x]==x) return x;
    return parent[x]=Find(parent[x]);
}
void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    parent[x]=y;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1; i <=m ; i++){
        parent[i]=i;
    }

    for(int i=1 ; i <= n ; i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(!visit[x]){
            visit[x]=true;
            Union(x,y);
            printf("LADICA\n");
        }
        else if(!visit[y]){
            visit[y]=true;
            Union(y,x);
            printf("LADICA\n");
        }
        else if(!visit[Find(x)]){
            visit[Find(x)]=true;
            Union(x,y);
            printf("LADICA\n");
        }
        else if(!visit[Find(y)]){
            visit[Find(y)]=true;
            Union(y,x);
            printf("LADICA\n");
        }
        else{
            printf("SMECE\n");
        }
    }
}