์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
- ์ด๋ถ ํ์
- error
- ๋ฐฑํธ๋ํน
- ๋ถํ ์ ๋ณต
- thymeleaf
- BFS
- CVE
- GCP
- ์คํ
- web
- OS
- ๊ทธ๋ฆฌ๋
- ์ต๋จ ๊ฒฝ๋ก
- dfs
- ๋ฌธ์์ด
- JPA
- ์ฐ์ ์์ ํ
- c++
- ๋งต
- ๊ตฌํ
- java
- ์์ ์ ๋ ฌ
- Spring
- dynamic debugging
- ๋ฐ์ดํฌ์คํธ๋ผ
- DP
- ์๋ฎฌ๋ ์ด์
- Reversing
- ์ฌ๊ท
- ๋์ ํฉ
- Today
- Total
hades
[Baekjoon] 1043๋ฒ: ๊ฑฐ์ง๋ง ๋ณธ๋ฌธ
๐ฅ ๋ฌธ์
https://www.acmicpc.net/problem/1043
๐ ์ค๊ณ
ํํฐ์ ์ต์ข ์ ์ผ๋ก ์ง์ค์ ์๊ฒ ๋๋ ์ฌ๋์ด ํ ๋ช ์ด๋ผ๋ ์์ผ๋ฉด, ๊ฑฐ์ง๋ง์ ํ ์ ์๋ค.
ํํฐ์ ์ง์ค์ ์๋ ์ฌ๋์ ๋จผ์ ์ฐพ๊ณ , ์์ผ๋ฉด ํํฐ์ ์๋ ์ฌ๋๋ค์ ์ง์ค์ ์๋ ์ฌ๋๋ค์ ์งํฉ์ผ๋ก union ํ๋ ค๊ณ ํ๋๋ฐ, ์ด ๋ฐฉ๋ฒ์ ํํฐ ์ค ๋ค์ ์ง์ค์ ์๋ ์ฌ๋์ด ์์ผ๋ฉด, ์์ ํํฐ์์๋ ์ง์ค์ ์๋ ์ฌ๋๋ค์ ์งํฉ์ผ๋ก unionํ ์ ์๋ค.
๋จ์ํ๊ฒ ํํฐ์ ์๋ ์ฌ๋๋ค์ ๋ฌถ๊ธฐ๋ง ํ๋ฉด, ์ง์ค์ ์๋ ์ฌ๋์ด ๋ค์ชฝ ํํฐ์ ๋์๋ ๋ค์ชฝ ํํฐ์์ ์ง์ค์ ์๋ ์ฌ๋๋ค์ ์งํฉ์ผ๋ก ๋ฐ์๋๊ธฐ ๋๋ฌธ์, ํํฐ ๊ฐ๊ฐ์์ ์ง์ค์ ์๋ ์ฌ๋์ด ์์ผ๋ฉด ์ด ํํฐ ์์์ ๊ฐ์์ํค๊ธฐ๋ง ํ๋ฉด ๋๋ค.
๐ ํ์ด
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, number, person, result = 0;
vector<int> parent(51);
vector<vector<int>> parties;
int find_parent(int x) {
if (parent[x] != x) {
return find_parent(parent[x]);
}
return x;
}
void union_parent(int a, int b) {
a = find_parent(a);
b = find_parent(b);
if (a < b) {
parent[b] = a;
}
else {
parent[a] = b;
}
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
cin >> number;
if (number == 0) {
cout << m << "\n";
return 0;
}
for (int i = 0; i < number; i++) {
cin >> person;
parent[person] = 0;
}
for (int i = 0; i < m; i++) {
vector<int> party;
cin >> number;
for (int j = 0; j < number; j++) {
cin >> person;
party.push_back(person);
}
for (int j = 1; j < number; j++) {
union_parent(party[0], party[j]);
}
parties.push_back(party);
}
int result = m;
for (int i = 0; i < m; i++) {
for (int j = 0; j < parties[i].size(); j++) {
if (find_parent(parties[i][j]) == 0) {
result -= 1;
break;
}
}
}
cout << result << "\n";
return 0;
}
'๐ PS > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 1167๋ฒ: ํธ๋ฆฌ์ ์ง๋ฆ (0) | 2024.08.02 |
---|---|
[Baekjoon] 1149๋ฒ: RGB๊ฑฐ๋ฆฌ (0) | 2024.08.02 |
[Baekjoon] 28702๋ฒ: FizzBuzz (0) | 2024.07.31 |
[Baekjoon] 30804๋ฒ: ๊ณผ์ผ ํํ๋ฃจ (0) | 2024.07.30 |
[Baekjoon] 17626๋ฒ: Four Squares (0) | 2024.07.29 |