글 읽기 - 4195 질문

tbn23 2년 전 0

저 코드에서

처음에는 find(min(li,ri))와 find(max(li,ri))를 비교해서 했는데 정답이 떳습니다

근데 union find를 할때 find(li)와 find(ri)를 비교해야 될 것같아서

min(find(li),find(ri))와 max(find(li),find(ri))를 이용해서 했는데 정답이 떳습니다.

뭐를 이용해도 상관이 없는거였나요?

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string.h>

using namespace std;
int uni[200000];
int num[200000];
int find(int x){
    if(x == uni[x]){
        return x;
    }
    uni[x] = find(uni[x]);
    return uni[x];
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int f,n;
        string c[200000];
        string lf,rf;
        vector<string> s; // sorting
        priority_queue<string,vector<string>,greater<string>> a; // 모든것 다 처넣기
        int i,j,k;
        int l,r,mid;
        int li,ri;
        
        scanf("%d",&f);
        for(i=0; i<2*f; i++){
            cin >> c[i];
            a.push(c[i]);
        }
        while(!a.empty()){
            //cout << a.top() << endl;
            if(s.empty() || s[s.size()-1] != a.top()){
                s.push_back(a.top());
            }
            a.pop();
        }
        
        n = s.size();
        for(i=0; i<n; i++){
            uni[i] = i;
            num[i] = 1;
            //cout << s[i] + " ";
        }
        //printf("\n");
        for(i=0; i<f; i++){
            lf = c[i*2]; rf = c[i*2+1];
            //cout << "lf : " + lf << " rf : " + rf << endl;
            l=0; r=n-1;
            while(l < r){
                mid = (l+r)/2;
                if(s[mid] < lf){
                    l = mid + 1;
                }
                else{
                    r = mid;
                }
            }
            li = l;
            l=0; r=n-1;
            while(l < r){
                mid = (l+r)/2;
                if(s[mid] < rf){
                    l = mid + 1;
                }
                else{
                    r = mid;
                }
            }
            ri = l;
            //printf("li : %d ri : %d\n",li,ri);
            if(find(li) != find(ri)){
                num[min(find(li),find(ri))] += num[max(find(li),find(ri))];
                uni[max(find(li),find(ri))] = min(find(li),find(ri));
            }
            printf("%d\n",num[find(li)]);
        }
    }
}

slah007 2년 전 0

A==B와 max(A,B)==min(A,B)는 같은 조건입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

4195 질문

tbn23 2년 전 0

slah007 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말