Skip to content

Commit 96320bd

Browse files
ndb796ndb796
committed
Update
1 parent 67be43e commit 96320bd

File tree

8 files changed

+285
-0
lines changed

8 files changed

+285
-0
lines changed

‎10/1.cpp‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
6+
// 노드의 개수는 최대 100,000개라고 가정
7+
int v, e;
8+
int parent[100001]; // 부모 테이블 초기화하기
9+
10+
// 특정 원소가 속한 집합을 찾기
11+
int findParent(int x) {
12+
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
13+
if (x == parent[x]) return x;
14+
return findParent(parent[x]);
15+
}
16+
17+
// 두 원소가 속한 집합을 합치기
18+
void unionParent(int a, int b) {
19+
a = findParent(a);
20+
b = findParent(b);
21+
if (a < b) parent[b] = a;
22+
else parent[a] = b;
23+
}
24+
25+
int main(void) {
26+
cin >> v >> e;
27+
28+
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
29+
for (int i = 1; i <= v; i++) {
30+
parent[i] = i;
31+
}
32+
33+
// Union 연산을 각각 수행
34+
for (int i = 0; i < e; i++) {
35+
int a, b;
36+
cin >> a >> b;
37+
unionParent(a, b);
38+
}
39+
40+
// 각 원소가 속한 집합 출력하기
41+
cout << "각 원소가 속한 집합: ";
42+
for (int i = 1; i <= v; i++) {
43+
cout << findParent(i) << ' ';
44+
}
45+
cout << '\n';
46+
47+
// 부모 테이블 내용 출력하기
48+
cout << "부모 테이블: ";
49+
for (int i = 1; i <= v; i++) {
50+
cout << parent[i] << ' ';
51+
}
52+
cout << '\n';
53+
}

‎10/2.cpp‎

Whitespace-only changes.

‎10/2.java‎

Whitespace-only changes.

‎10/2.py‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
def find_parent(parent, x):
2+
if parent[x] != x:
3+
parent[x] = find_parent(parent, parent[x])
4+
return parent[x]

‎10/3.cpp‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
6+
// 노드의 개수는 최대 100,000개라고 가정
7+
int v, e;
8+
int parent[100001]; // 부모 테이블 초기화하기
9+
10+
// 특정 원소가 속한 집합을 찾기
11+
int findParent(int x) {
12+
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
13+
if (x == parent[x]) return x;
14+
return parent[x] = findParent(parent[x]);
15+
}
16+
17+
// 두 원소가 속한 집합을 합치기
18+
void unionParent(int a, int b) {
19+
a = findParent(a);
20+
b = findParent(b);
21+
if (a < b) parent[b] = a;
22+
else parent[a] = b;
23+
}
24+
25+
int main(void) {
26+
cin >> v >> e;
27+
28+
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
29+
for (int i = 1; i <= v; i++) {
30+
parent[i] = i;
31+
}
32+
33+
// Union 연산을 각각 수행
34+
for (int i = 0; i < e; i++) {
35+
int a, b;
36+
cin >> a >> b;
37+
unionParent(a, b);
38+
}
39+
40+
// 각 원소가 속한 집합 출력하기
41+
cout << "각 원소가 속한 집합: ";
42+
for (int i = 1; i <= v; i++) {
43+
cout << findParent(i) << ' ';
44+
}
45+
cout << '\n';
46+
47+
// 부모 테이블 내용 출력하기
48+
cout << "부모 테이블: ";
49+
for (int i = 1; i <= v; i++) {
50+
cout << parent[i] << ' ';
51+
}
52+
cout << '\n';
53+
}

‎10/4.cpp‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
6+
// 노드의 개수는 최대 100,000개라고 가정
7+
int v, e;
8+
int parent[100001]; // 부모 테이블 초기화하기
9+
10+
// 특정 원소가 속한 집합을 찾기
11+
int findParent(int x) {
12+
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
13+
if (x == parent[x]) return x;
14+
return parent[x] = findParent(parent[x]);
15+
}
16+
17+
// 두 원소가 속한 집합을 합치기
18+
void unionParent(int a, int b) {
19+
a = findParent(a);
20+
b = findParent(b);
21+
if (a < b) parent[b] = a;
22+
else parent[a] = b;
23+
}
24+
25+
int main(void) {
26+
cin >> v >> e;
27+
28+
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
29+
for (int i = 1; i <= v; i++) {
30+
parent[i] = i;
31+
}
32+
33+
bool cycle = false; // 사이클 발생 여부
34+
35+
for (int i = 0; i < e; i++) {
36+
int a, b;
37+
cin >> a >> b;
38+
// 사이클이 발생한 경우 종료
39+
if (findParent(a) == findParent(b)) {
40+
cycle = true;
41+
break;
42+
}
43+
// 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
44+
else {
45+
unionParent(a, b);
46+
}
47+
}
48+
49+
if (cycle) {
50+
cout << "사이클이 발생했습니다." << '\n';
51+
}
52+
else {
53+
cout << "사이클이 발생하지 않았습니다." << '\n';
54+
}
55+
}

‎10/5.cpp‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
6+
// 노드의 개수는 최대 100,000개라고 가정
7+
int v, e;
8+
int parent[100001]; // 부모 테이블 초기화하기
9+
// 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
10+
vector<pair<int, pair<int, int> > > edges;
11+
int result = 0;
12+
13+
// 특정 원소가 속한 집합을 찾기
14+
int findParent(int x) {
15+
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
16+
if (x == parent[x]) return x;
17+
return parent[x] = findParent(parent[x]);
18+
}
19+
20+
// 두 원소가 속한 집합을 합치기
21+
void unionParent(int a, int b) {
22+
a = findParent(a);
23+
b = findParent(b);
24+
if (a < b) parent[b] = a;
25+
else parent[a] = b;
26+
}
27+
28+
int main(void) {
29+
cin >> v >> e;
30+
31+
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
32+
for (int i = 1; i <= v; i++) {
33+
parent[i] = i;
34+
}
35+
36+
// 모든 간선에 대한 정보를 입력 받기
37+
for (int i = 0; i < e; i++) {
38+
int a, b, cost;
39+
cin >> a >> b >> cost;
40+
// 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
41+
edges.push_back({cost, {a, b}});
42+
}
43+
44+
// 간선을 비용순으로 정렬
45+
sort(edges.begin(), edges.end());
46+
47+
// 간선을 하나씩 확인하며
48+
for (int i = 0; i < edges.size(); i++) {
49+
int cost = edges[i].first;
50+
int a = edges[i].second.first;
51+
int b = edges[i].second.second;
52+
// 사이클이 발생하지 않는 경우에만 집합에 포함
53+
if (findParent(a) != findParent(b)) {
54+
unionParent(a, b);
55+
result += cost;
56+
}
57+
}
58+
59+
cout << result << '\n';
60+
}

‎10/6.cpp‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
#include <bits/stdc++.h>
2+
3+
using namespace std;
4+
5+
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
6+
// 노드의 개수는 최대 100,000개라고 가정
7+
int v, e;
8+
// 모든 노드에 대한 진입차수는 0으로 초기화
9+
int indegree[100001];
10+
// 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
11+
vector<int> graph[100001];
12+
13+
// 위상 정렬 함수
14+
void topologySort() {
15+
vector<int> result; // 알고리즘 수행 결과를 담을 리스트
16+
queue<int> q; // 큐 라이브러리 사용
17+
18+
// 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
19+
for (int i = 1; i <= v; i++) {
20+
if (indegree[i] == 0) {
21+
q.push(i);
22+
}
23+
}
24+
25+
// 큐가 빌 때까지 반복
26+
while (!q.empty()) {
27+
// 큐에서 원소 꺼내기
28+
int now = q.front();
29+
q.pop();
30+
result.push_back(now);
31+
// 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
32+
for (int i = 0; i < graph[now].size(); i++) {
33+
indegree[graph[now][i]] -= 1;
34+
// 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
35+
if (indegree[graph[now][i]] == 0) {
36+
q.push(graph[now][i]);
37+
}
38+
}
39+
}
40+
41+
// 위상 정렬을 수행한 결과 출력
42+
for (int i = 0; i < result.size(); i++) {
43+
cout << result[i] << ' ';
44+
}
45+
}
46+
47+
int main(void) {
48+
cin >> v >> e;
49+
50+
// 방향 그래프의 모든 간선 정보를 입력 받기
51+
for (int i = 0; i < e; i++) {
52+
int a, b;
53+
cin >> a >> b;
54+
graph[a].push_back(b); // 정점 A에서 B로 이동 가능
55+
// 진입 차수를 1 증가
56+
indegree[b] += 1;
57+
}
58+
59+
topologySort();
60+
}

0 commit comments

Comments
 (0)