글 읽기 - 친구 네트워크(Disjoint set) 왜 틀렸는지 모르겠습니다ㅠㅠ

chocoo 4년 전 0

처음에는 시간초과 나길래 iostream 처리해주었는데 틀리네요...

Disjoint set으로 구현해주었는데,

테케도 다 맞아서 어디가 틀렸는지 모르겠습니다ㅜㅜ

지식 나눠주시면 큰 도움이 되겠습니다!

#include <iostream>
#include <map>
using namespace std;

int parent[200001];
int num[200001];

int find(int idx)
{
    if(idx==parent[idx]) return idx;
    return parent[idx] = find(parent[idx]);
}

int merge(int f1,int f2)
{
    int pf1 = find(f1);
    int pf2 = find(f2);

    //한쪽으로 몰아주기
    if(pf1!=pf2)
    {
      num[pf1]+=num[pf2];
      num[pf2]=num[pf1]; //같은 갯수 가지도록. num[pf2]=1도 틀림..
      parent[f2]=pf1;
    }
    return num[pf1];
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int tc=0;
    cin>>tc;
    while(tc--)
    {
        int n=0,idx=0;
        map<string,int> friend_;
        string f1; string f2;
        cin>>n;

        for(int j=1; j<2*n+1;j++)
        {
            num[j]=1; 
            parent[j]=j;
        }
        for(int i=0; i<n; i++)
        {   
            cin>>f1;
            cin>>f2;
            if(friend_.find(f1)==friend_.end())
                 friend_[f1]=++idx;
               
            if(friend_.find(f2)==friend_.end())
                 friend_[f2]=++idx;

             cout<<merge(friend_[f1],friend_[f2])<<'\n';
        }
    }
    return 0;
}

ha_ram 4년 전 1

24번째줄을

parent[pf2]=pf1;

로 바꿔주면 됩니다.

chocoo 4년 전 1

부모의 부모를 변경해 주는 것을 잊었네요...

큰 도움이 되었습니다 정말 감사합니다!

좋은 하루 되세요

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

문제

문제

출처

ICPC

친구 네트워크(Disjoint set) 왜 틀렸는지 모르겠습니다ㅠㅠ

chocoo 4년 전 0

ha_ram 4년 전 1

chocoo 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말