Algorithm/그래프

리트코드 133 그래프 클론 c++ // 그래프 복사하는방법

https://leetcode.com/problems/clone-graph/description/ 1. 의사코드1. map에 를 담는다.2. 엣지케이스 : 원래널인경우 return nullroot에 이웃이없는경우, 그거 new로 생성해서 리턴3. dfs초기화 : cur(원본)배열의 값으로 노드를 만들어주고, 이웃만 채워주면 된다!!이웃에대해, 이미 클론되었다면(맵에 존재한다면 == 유사 visited) 이웃에 담아준다.아니라면, 거기로 들어간다.4. 아래그림에서 1에서 시작하는 dfs를 돌려보면 이해가 될것이다.class Solution {public: Node* dfs(Node* cur, unordered_map& mp) { vector neighbour; Node* c..

프로그래머스 도넛과막대그래프 c++ // 그래프 차수 특징발견, 사이클검사방법, 최대번호노드 찾는방법

https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1. 그래프 차수 특징발견각 그래프마다 대표정점의 특징(고유한 degree값)이 존재한다.해당정점의 갯수가 그 그래프의 갯수이다!0. 모든그래프의 갯수 == 시작점에서 뻗어나가는 간선갯수와 같다.4에서 위로가는 집합 : a모양좌로가는 집합 : b모양우로가는 집합 : c모양이 된다.즉, 3개의 집합이 도넛인지, 뭔지 찾으면 된다.1. 도넛그래프out, indegree가 같다, but 대표정점이 없다. ..

백준 1717 집합의표현 c++ // 유니온 파인드 구현방법

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 1. 의사코드 *파인드 : 자기자신이 부모임 == 루트노드 아님 : 부모의 조상을 찾아서 리턴 *유니언 : 조상이다를때, 작은쪽으로 합침 rootA의 부모 = rootB // parent[rootA]=rootB ※ A의 부모 = rootB 가 아님에 주의! // parent[A]=rootB (X) #include using namespace std; int n..