전체 글 썸네일형 리스트형 단절점(Articulation Point)와 단절선(Bridge) 하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상의 컴포넌트로 나누어지는 정점을 단절점이라고 합니다.다음과 같은 무방향 그래프가 있다고 해봅시다. 여기서 빨간색 테두리로 이루어진 정점들중 하나를 지울 경우 컴포넌트가 2개로 나누어지게 됩니다. 이러한 성질을 가지는 정점들을 단절점이라고 부릅니다. 그러면 우리는 단절점을 어떤 방법으로 찾을 수 있을까요? 우선은 단절점을 찾기 위해서 우선 단절점이 가지는 특징을 알아야 됩니다. 아까의 그래프에서 단절점인 빨간정점에 연결된 정점들을 초록정점으로 색칠해봤습니다. 우리는 어떤 정점 A에 연결된 모든 정점들 중 두 정점들 간에 정점 A를 거치지않고 갈 수 있는 우회경로가 존재하지 않는 경우가 존재한다면 정점 A는 단절점으로 판단.. 더보기 BOJ)3682 동치 증명 문제: icpc.me/3682 그래프에서 동치임을 증명하기 위해 사용하는 함축의 수의 최솟값을 출력하는 문제이다. 우리는 동치임을 증명하기 위해서 그래프의 사이클을 생성해주면 된다. 우리는 그래프의 SCC를 분류한 뒤 다시 SCC들을 정점으로 가지는 그래프로 압축하여 각 SCC의 indegree와 outdegree의 수를 구해준 뒤 indegree가 0인 정점과 outdegree가 0인 정점중 최댓값을 출력해주면 된다. 그래프의 사이클을 만들어야 하기 때문에 사이클이 존재하려면 indegree와 outdegree가 적어도 1씩 존재해야 하기 때문이다. 단 그래프가 하나의 SCC를 이룰 경우는 예외처리를 해주어야만 한다. 12345678910111213141516171819202122232425262728.. 더보기 BOJ)11338 XOR Sum 문제: icpc.me/11338 n개의 쿼리가 주어질 때 2가지 쿼리에 따라서 문제를 해결하는 문제이다. insert 쿼리는 리스트에 숫자를 추가하는것이며 print 쿼리는 리스트 중에 상위 K숫자를 XOR한 값을 출력하는 문제이다. 우리는 매 print마다 리스트에서 XOR을 할 경우 시간초과가 나므로 insert 될 때 마다 모든 값을 XOR해준 뒤 minheap을 이용하여 리스트 숫자가 K를 초과할때 마다 최솟값을 XOR해준다. 이는 A^X^X=A가 되는 원리를 이용하는 풀이이다. 1234567891011121314151617181920212223242526272829303132#include #include #include using namespace std;char a[7];int t, m, k.. 더보기 이전 1 ··· 83 84 85 86 87 88 89 ··· 118 다음
