0x16강 - 이진 검색 트리

[Jinsun-Lee]

리드미

• 큰돌: 그래프, 트리, 인접행렬, 인접리스트, DFS, BFS
• 0x16강 - 이진 검색 트리
• 0x18강 - 그래프
• 0x19강 - 트리

[Jinsun-Lee]

추가 풀이한 문제 (리드미에 없음)

• [x]

[Jinsun-Lee]

해치워

• 간선리스트, 인접행렬, 인접리스트
• 코테합: 트리, 집합, 그래프

[Jinsun-Lee]

• 트리의 부모 찾기
• 트리: 트리의 개수 세기 = 사이클이 없으면 카운팅
• 트리와 쿼리: 서브트리에 속한 정점의 수 세기
• [ ]

[Jinsun-Lee]

⭐트리의 부모 찾기

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int MX = 100'001;

int N;
vector<int> tree[MX];
int Parents[MX];
bool visit[MX];

void BFS(int start) {
    queue<int> q;
    q.push(start);

    visit[start] = 1;

    while (!q.empty()) {
        int parent = q.front(); q.pop();

        for (int i = 0; i < tree[parent].size(); ++i) {
            int child = tree[parent][i];

            if (visit[child]) continue;
            visit[child] = true;

            Parents[child] = parent;
            q.push(child);
        }
    }
}

void DFS(int start) {
    visit[start] = 1;

    for (int i = 0; i < tree[start].size(); ++i) {
        int child = tree[start][i];

        if (visit[child]) continue;
        
        Parents[child] = start;
        DFS(child);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    freopen_s(new FILE*, "input.txt", "r", stdin);

    cin >> N;
    int u, v;
    for (int i = 0; i < N - 1; ++i) { // N-1까지 주의 
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    //BFS(1);
    DFS(1);
    for (int i = 2; i <= N; ++i) cout << Parents[i] << "\n"; // 범위랑 그냥 i 출력 

    return 0;
}

[Jinsun-Lee]

트리

틀린 게 없는 거 같아서 진짜 뭐지 하면서 시간 버렸는데...
진짜 합치려고 하지 마라...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MX = 501;

int N, M; // 정점, 간선, m줄 간선의 연결
int Parents[MX];
bool visit[MX];

bool DFS(const vector<vector<int>>& graph, int cur) { // 싸이클 여부를 리턴
	// visit[start] = 1;

	for (int i = 0; i < graph[cur].size(); ++i) {
		int nxt = graph[cur][i];

		// nxt가 부모가 아닌데 방문했으면 cycle = true; continue;
		if (nxt == Parents[cur]) continue; // 부모 노드로 올라가지 마
		if (visit[nxt]) return true; // 사이클 발견
		
		visit[nxt] = 1;
		Parents[nxt] = cur;
		
		//DFS(graph, nxt);
		if (DFS(graph, nxt)) return true; // 재귀에서 싸이클 발생 시 중단하게 해야 해
	}
	return false; // 싸이클이 없어야 트리
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int u, v, tc = 1;
	while (1) {
		cin >> N >> M;
		if (N == 0 && M == 0) break; // 종료 조건

		vector<vector<int>> graph(N + 1);
		fill(Parents, Parents+MX, 0);
		fill(visit, visit +MX, false);

		while (M--) {
			cin >> u >> v;
			graph[u].push_back(v);
			graph[v].push_back(u);
		}

		int ans = 0;
		for (int i = 1; i <= N; ++i) { // 범위 주의
			if (visit[i]) continue;
			visit[i] = 1; // 여기에서 갱신

			if (DFS(graph, i) == false) ++ans; // 싸이클이 없을 때에만
		}

		cout << "Case " << tc++ << ": ";
		if (ans == 0) cout << "No trees.\n";
		else if (ans == 1) cout << "There is one tree.\n";
		else cout << "A forest of " << ans << " trees.\n";
	}

	return 0;
}

vector<int> graph[MX];

bool DFS(int cur, int prev) {
	for (int nxt : graph[cur]){
	//for (int i = 0; i < graph[cur].size(); ++i) {
		//int nxt = graph[cur][i];

		if (nxt == prev) continue;
		if (visit[nxt]) return true;
		
		visit[nxt] = 1;
		if (DFS(nxt, cur)) return true; 
	}
	return false; 
}

int main() {
	while (1) {
		cin >> N >> M;
		for (int i = 1; i <= N; ++i) graph[i].clear(); // 범위랑 초기화 주의
		...
}

vector<int> tree[MX];
int n, m, vis[MX];

bool bfs(int start) {
	queue<int> q;
	q.push(start);
	vis[start] = -1; // 시작 노드의 부모가 없음을 음수로 표시

	while (!q.empty()) {
		int cur = q.front(); q.pop(); 

		//for (int i = 0; i < tree[cur].size(); ++i) {
		for (int nxt : tree[cur]){
			if (nxt == vis[cur]) continue; // 부모 노드로 올라가지 마

			if (vis[nxt]) return true; // 이미 방문했을 경우 사이클
			vis[nxt] = cur; // 부모를 저장
			q.push(nxt);
		}
	}
	return false; // 사이클 없음 = 트리
}

int main() {
	for (int i = 0; i < MX; ++i) tree[i].clear(); //tree->clear();
}

[Jinsun-Lee]

트리와 쿼리

매 쿼리마다 BFS 돌리지 마
서브트리의 정점 개수 = 연결된 노드의 수 + 자기 자신
무방향 그래프에서 사이클=어떤 정점에서 시작해서, 한번씩만 방문해서 시작점으로 돌아올 수 있는 경로

[Jinsun-Lee]

[Jinsun-Lee]

[Jinsun-Lee]

[Jinsun-Lee]

[Jinsun-Lee]

[Jinsun-Lee]

<details><summary>⭐</summary>

<br>

```cpp

```
</details>