데이터 구조 - 트 리 (기본)

1. 뿌리 없 는 나무 에서 뿌리 있 는 나무 로

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
#include <vector>
using namespace std;

const int maxn = 1000005;
int p[maxn];
int n;
int root;

vector<int> G[maxn];
void read_tree() {	//      
	int u, v;
	scanf("%d", &n);
	for(int i = 0; i < n - 1; i++) {
		scanf("%d %d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
}

void dfs(int u, int fa) {	//     u     ，u    fa 
	int d = G[u].size();
	for(int i = 0; i < d; i++) {	//  u       
		int v = G[u][i];			//  u  i    v 
		if(v != fa) dfs(v, p[v] = u);	 // v     u，       v      
	}
}

int main() {
	//freopen("in.txt", "r", stdin);
	read_tree();
	
	scanf("%d", &root);
	p[root] = -1;
	
	dfs(root, -1);
	
	for(int i = 0; i < n; i++) {
		printf("%d ", p[i]);
	}
	return 0;
}

2. 표현 식 트 리

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
using namespace std;

char str[10005]; 

const int maxn = 1000;
int lch[maxn], rch[maxn];	//               
char op[maxn];
int nc;		//    

int build_tree(char * s, int x, int y) {
	int i, c1 = -1, c2 = -1, p = 0;
	int u;
	if(y - x == 1) {	//     ，       
		u = ++nc;
		lch[u] = rch[u] = 0;
		op[u] = s[x];
		return u;
	} 
	for(int i = x; i < y; i++) {
		switch(s[i]) {
			case '(': p++; break;
			case ')': p--; break;
			case '+': case '-': if(!p) c1 = i; break;
			case '*': case '/': if(!p) c2 = i; break;
		}
	}
	
	if(c1 < 0) c1 = c2;
	if(c2 < 0) return build_tree(s, x + 1, y - 1);
	u = ++nc;
	lch[u] = build_tree(s, x, c1);
	rch[u] = build_tree(s, c1 + 1, y);
	op[u] = s[c1];
	return u;
}

int main() {
	while(scanf("%s", str) != EOF) {
		nc = 0;
		int len = strlen(str);
		op[0] = build_tree(str, 0, len);
		for(int i = 1; i <= nc; i++) {
			printf("%c ", op[i]);
		}
	}
	return 0;
}

3. 최소 생 성 트 리 (MST, kruskal)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
using namespace std;

struct edge {
	int a, b, w;	
}e[10005];

int pa[1000005];
int n, m;

int cmp(edge a, edge b) {	//       
	return a.w < b.w;
}

int find(int x) {	//      
	return x == pa[x] ? x : pa[x] = find(pa[x]);
}

int join(edge e) {		//      
	int x = find(e.a), y = find(e.b);
	if(x != y) {
		pa[x] = y;
		return e.w;
	}
	return 0;
}

int kruskal() {		//kruskal   MST 
	int ans = 0;
	for(int i = 0; i < n; i++) pa[i] = i;//       
	sort(e, e + m, cmp);//     
	for(int i = 0; i < n; i++) ans += join(e[i]);
	return ans;
}

int main() {
	while(scanf("%d %d", &n, &m) != EOF) {	//n  ，m   
		for(int i = 0; i < m; i++) {
			scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].w);
		} 
		printf("%d
", kruskal());
	}
	return 0;
}