mintuchel mintuchel

#include #define SIZE 1000001 using namespace std; int arr[SIZE]; // 부모노드 찾는 함수 // 부모노드 찾으면서 해당 경로에 있는 노드들의 부모노드도 업데이트 int find(int node) { // 자기 자신이면 자기꺼 반환 if (arr[node] == node) return node; else { // 아니면 재귀로 찾기 // 찾으면서 경로에 있는 모든 노드들의 부모노드 업데이트 arr[node] = find(arr[node]); } return arr[node]; } // a a 로 들어가야함 void add(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (a < b) ar..

DFS 재귀로 풀어주면 된다. 맨 밑 leaf node까지 재귀로 내려가준 다음에, 해당 노드부터 생존수를 계산하여 루트노드까지 올려보내면 된다 일단 조건을 보면 한 섬에는 양 또는 늑대가 삼. 즉 둘 중 하나임. 조건 상 뭐든 살아 그래서 양이면 num을 +값으로 놓고 늑대면 num을 음수로 놓으면 됨 부호가 양/늑대 구분하는 기준인거임 그리고 양이 다 죽으면 0이지 -200 이런 숫자는 말이 안되니까 sum 조건 상 이게 늑대든 양이든 뭐든 살아 int arr[SIZE]; vector tree[SIZE]; bitset visited; long long DFS(int v) { visited[v] = 1; long long sum = 0; for (auto it = tree[v].begin(); it !..

C++에는 트리에 대한 STL이 따로 없다. 그래서 있는 걸로 만들어야함 근데 이걸 자료구조 수업때 한 것처럼 죄다 Node 구조체 껴서 만드는건 미친짓임 ㅇㅇ... 인접행렬은 시간복잡도랑 공간복잡도가 개쓰레기 수준이니 그냥 vector 배열이나 unordered_map으로 인접리스트형식을 구현해주면 됨 난 vector 배열 구현을 더 선호. 시간이 더 적게 걸림 트리 부모 찾는데 다른 단순한 방법이 있을까 생각해봤는데 없다. 우선 DFS로 품. DFS 하면서 해당 자식 찾으면 해당 자식의 노드list로 들어가기 전에 stack에 현재 위치만 push해주면 됨.1. DFS#include #include #include #define SIZE 100001 using namespace std; int arr..