tree (9) 썸네일형 리스트형 [BOJ] 1967번 트리의 지름 (C++) https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net #include #include using namespace std; int n; vector tree[10001]; bool visited[10001]; int max_len = 0; int end_node = 0; void dfs(int node, int len) { if (visited[node]) return; visited[node] = true; if (len > m.. [BOJ] 1068번 트리 (C++) https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net #include #include using namespace std; vector tree[50]; int n, k, root; int leafcnt = 0; int dfs(int node){ if(node == k) return -1; if(tree[node].size() == 0){ leafcnt++; return 0; } for(int i = 0; i < tree[node].size().. [BOJ] 2263번 트리의 순회 (C++) https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net #include using namespace std; int Index[100001]; int inOrder[100001]; int postOrder[100001]; void getPreOrder(int inStart, int inEnd, int postStart, int postEnd){ if(inStart > inEnd || postStart > postEnd) return; int rootIndex = Index[po.. [BOJ] 11725번 트리의 부모 찾기 (C++) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net #include #include #include using namespace std; int parent[100001]; bool visited[100001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector node[100001]; for(int i = 0; i > x >> y; node[x].push_back.. [BOJ] 1761번 정점들의 거리 (C++) https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net #include #include #include using namespace std; int parent[40001]; int depth[40001]; int length[40001]; bool visited[40001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector node[40001];.. [BOJ] 3584번 가장 가까운 공통 조상 (C++) https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #include using namespace std; int parent[10001]; bool visited[10001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; for(int j = 0; j > n; // 초기.. [BOJ] 14267번 회사 문화 1 (C++) https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net #include #include #define MAX 100001 using namespace std; int n, m; vector v[MAX]; int cpm[MAX]; void dfs(int num){ for(int i = 0; i < v[num].size(); i++){ cpm[v[num][i]] += cpm[num]; dfs(v[num][i]); } } int main() { ios::.. [BOJ] 15681번 트리와 쿼리 (C++) https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net #include #include #define MAX 100001 using namespace std; int dp[MAX]; vector vec[MAX]; bool visited[MAX]; void dfs(int node, int parent){ visited[node] = true; for(int i = 0; i < vec[node.. 이전 1 2 다음
