본문 바로가기

타잔 알고리즘

BOJ)3682 동치 증명 문제: icpc.me/3682 그래프에서 동치임을 증명하기 위해 사용하는 함축의 수의 최솟값을 출력하는 문제이다. 우리는 동치임을 증명하기 위해서 그래프의 사이클을 생성해주면 된다. 우리는 그래프의 SCC를 분류한 뒤 다시 SCC들을 정점으로 가지는 그래프로 압축하여 각 SCC의 indegree와 outdegree의 수를 구해준 뒤 indegree가 0인 정점과 outdegree가 0인 정점중 최댓값을 출력해주면 된다. 그래프의 사이클을 만들어야 하기 때문에 사이클이 존재하려면 indegree와 outdegree가 적어도 1씩 존재해야 하기 때문이다. 단 그래프가 하나의 SCC를 이룰 경우는 예외처리를 해주어야만 한다. 12345678910111213141516171819202122232425262728.. 더보기
SCC(Strongly Connected Component) 방향 그래프에서 어떤 그룹 X에 있는 임의의 두 정점 A,B에 대해서 항상 A->B로 가는 경로가 존재한다면 그 그룹을 SCC(Strongly Connected Component)라 칭합니다. 더 정확하게 정의하자면 SCC가 되는 그룹은 항상 최대로 정의되기 때문에 다음과 같은 조건을 만족해야 합니다. 1. 같은 SCC 내의 임의의 두 정점 A,B사이의 경로가 항상 존재한다.2. 서로 다른 SCC에서 뽑은 임의의 두 점 A,B 사이의 경로 A->B로 가는 경로와 B->A로 가는 경로는 동시에 존재할 수 없다. (SCC 끼리는 사이클이 존재하지 않는다.) SCC를 직역하면 "강한 연결 요소" 라는 뜻이됩니다. 즉 SCC는 집합 내에서 정점들이 서로 왕복 가능한 최대 크기의 집합입니다. 다음과 같은 그래프에.. 더보기