글 읽기 - 친구 네트워크 질문드려요

tols91 7년 전 0

map 에 문자열을 키로 인덱스를 저장하고 있다가 disjoint set 에 넣으면서 친구관계를 찾게 했는데 시간

초과가 나네요.. ㅠㅠ 무엇이 문제일까요?

#include <cstdio>
#include <vector>
#include <map>
#include <string>
#include <cstring>
#include <iostream>

using namespace std;

struct DisjointSet
{
    vector<int> parent;
    vector<int> rank;
    vector<int> nodeCount;

    DisjointSet(int n) : parent(n+1), rank(n+1, 1), nodeCount(n+1, 1){
        for(int i=1;i<=n;i++)
            parent[i] = i;
    }

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

    void merge(int u, int v){
        u = find(u); v = find(v);

        if(u == v) return;

        if(rank[u] > rank[v]) swap(u,v);
        nodeCount[v] += nodeCount[u];
        parent[u] = v;
        if(rank[u] == rank[v]) rank[v]++;
    }

    int getNodeCount(int u){
        return nodeCount[u];
    }
};



int main()
{
    int T, N;
    scanf("%d", &T);
    string a, b;
    while(T--){
        scanf("%d",&N);
        DisjointSet dset(N+1);

        map<string, pair<int, int> > mp;

        int mark = 1;
        int a_index, b_index;

        while(N--){
	        cin >> a;
	        cin >> b;

	        if(mp[a].first == 0){
	            mp[a].first++;
	            mp[a].second = mark;
	            a_index = mark;
	            mark++;
	        }else{
	            a_index = mp[a].second;
	        }

	        if(mp[b].first == 0){
	            mp[b].first++;
	            mp[b].second = mark;
	            b_index = mark;
	            mark++;
	        }else{
	            b_index = mp[b].second;
	        }

	        dset.merge(a_index,b_index);
	        printf("%d\n", dset.getNodeCount(dset.find(a_index)));
    	}
    }
    return 0;
}

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

문제

문제

출처

ICPC

친구 네트워크 질문드려요

tols91 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말