[백준OJ] 4195번 친구 네트워크

[백준OJ] 4195번 친구 네트워크

728x90

반응형

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

풀이

입력받은 이름들을 숫자로 매핑해준뒤, Find-Union 알고리즘을 이용해서 네트워크를 연동시켜준다. 이때, 연결하고 카운팅을 하면 시간초과가 날 수 있으므로, 네트워크를 연결함과 동시에, 부모노드에 다른하나에 연결된 노드의 cnt를 더해준뒤, 부모노드의 cnt를 리턴해주면 시간초과가 나지 않고 값을 바로 구할 수 있게된다.

또한, 친구관계를 최대 100,000개 입력받는다 했으므로, parent배열은 최악의 수를 고려해서 2배인 200,001개를 할당해주어야 한다.

코드

#include #include #include #include using namespace std; typedef struct node { int pa; int cnt; }node; int t, n; node parent[200010]; int find(int a) { if (a == parent[a].pa) { return a; } else return find(parent[a].pa); } int union_parent(int a, int b) { a = find(a); b = find(b); //서로 다른 두 집합일때 if (a > b) { parent[a].pa = b;//집합 union parent[b].cnt += parent[a].cnt;//부모노드에 cnt 추가 return parent[b].cnt; } else if(a> t; while (t--) { map p; int total = 0; cin >> n; for (int i = 0; i < 200010; i++) { parent[i] = { i,1 }; } for (int i = 0; i < n; i++) { string n1, n2; cin >> n1 >> n2; if (!p[n1]) { p[n1] = ++total; } if (!p[n2]) { p[n2] = ++total; } int i1 = p[n1]; int i2 = p[n2]; cout << union_parent(i1, i2) << "

"; } } return 0; }

반응형

from http://khu98.tistory.com/251 by ccl(A) rewrite - 2021-08-30 01:26:31