codinging

Union Find 유니온 파인드란 그래프의 관점에서 두 노드가 같은 그래프에 속하는지 빠르게 판별하는 알고리즘이다. 집합에서의 관점으로는 두 요소가 같은 집합에 속하는지 판별한다. union find 알고리즘은 두 노드가 속하는 집합을 합치는 union 과 두 노드가 같은 집합인지 확인하는 find 연산이 있다. 설명 6개의 노드로 union find 의 예시를 들어보겠다. 부모를 알 수 있는 배열을 만드는데, 각 노드는 아직 아무 연결도 되어있지 않으므로 아직 자기자신이 부모이다. 1,2를 한 집합으로 4,5,6을 한 집합으로 묶고자 한다. 먼저 위의 예시는 잘못된 예시이다. 만약, 이런식으로 부모 노드를 연결한다면 문제가 생길 것 이다. 모든 노드를 연결 한다고 가정했을때 위와 같은 방식으로 부모노..

강한 연결 요소 그래프에서 강하게 연결 되어있는 집합이다. 같은 SCC집합에 속해있는 정점끼리는 도달가능하다는 특징을 가지고 있다. 집합내 모든 두 점이 서로 도달 가능할때 강하게 연결 되어있다고 한다. 위의 그림과 같은 그래프로 설명을 할 것 이다. 위의 그래프에서의 SCC는 다음 그림과 같은 집합으로 나타낼 수 있다. 같은 집합내의 원소들은 서로 도달가능하다. 예를들어 2와 4 를 보면 2는 4로 도달이 가능하지만 4는 2로 도달할 수 없기 때문에 2, 4는 같은 SCC가 아니다. 반면에, {1,2,3} 을 보면 1에서 2, 1에서 3 / 2에서 1 ,2에서 3/ 3에서 1, 3에서 2 어떤 두 정점을 잡아도 해당 노드로 이동이 가능하기 때문에 같은 SCC에 속한다고 보면 된다. 이제 SCC의 원소를..