ACM-ICPC 상 탈 사람

문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4393 오염된 물을 정화하기 위해서 단방향 그래프에서 0번 정점에서 나오는 정화제를 x개의 간선을 추가하여 모든 정점에 뿌려야할 때 연결해야하는 간선 x개의 최솟값을 구하는 문제이다. 이 문제는 정점들을 scc로 묶어준다음 위상정렬을 통하여 해결가능하다. 즉 0번 정점을 포함한 scc를 제외한 indegree가 0인 scc의 개수를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545..

문제: icpc.me/3682 그래프에서 동치임을 증명하기 위해 사용하는 함축의 수의 최솟값을 출력하는 문제이다. 우리는 동치임을 증명하기 위해서 그래프의 사이클을 생성해주면 된다. 우리는 그래프의 SCC를 분류한 뒤 다시 SCC들을 정점으로 가지는 그래프로 압축하여 각 SCC의 indegree와 outdegree의 수를 구해준 뒤 indegree가 0인 정점과 outdegree가 0인 정점중 최댓값을 출력해주면 된다. 그래프의 사이클을 만들어야 하기 때문에 사이클이 존재하려면 indegree와 outdegree가 적어도 1씩 존재해야 하기 때문이다. 단 그래프가 하나의 SCC를 이룰 경우는 예외처리를 해주어야만 한다. 12345678910111213141516171819202122232425262728..

문제: icpc.me/10265 K이하의 사람이 버스에 탈 수 있을 때 버스에 탈 수 있는 최대 인원을 출력하는 문제이다. 문제에는 조건이 있는데 A라는 사람은 B라는 사람이 버스에 안타면 A도 반드시 안타는 정보 N개가 주어진다. 우리는 이러한 조건을 B->A라는 방향 그래프로 만들어 준 SCC끼리 분류를 한다음 다음 위상 정렬을 이용하여 X라는 정점이 방문 가능한 모든점 Y는 반드시 X의 인원을 포함한다고 정의 가능하다. 이 때 X의 인원은 SCC의 그룹 크기와 동치가 된다. 따라서 연결 그래프마다 최소 인원~최대 인원 셋을 저장한 뒤 Knapsack문제를 해결하듯이 다이나믹 프로그래밍을 이용해주어 답을 계산해주면 된다. 이때 연결 그래프의 수는 SCC 그래프의 indegree가 0인 SCC의 개수이..

문제: icpc.me/3977 A->B로 이동해야하는 전술들이 주어질 때 시작 지점이 될 수 있는 위치를 찾는 문제이다. 이 때 적절한 시작지점이 없으면 Confused를 출력하면 된다. 여기서 SCC를 이루는 그룹이면 어떤 곳에서 시작하던 topology에 의해 나머지 지점들을 전부 탐색 가능하니 정점들을 SCC로 묶은 뒤 indegree가 0인 지점이 하나일 때는 해당 SCC에 속하는 모든 점들이 시작지점이 될 수 있고, 만약 indegree가 0인 지점이 여러곳일 경우에는 어떤 지점에서 시작해도 모든 점을 방문 불가능하기 때문에 Confused를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424..

문제:icpc.me/4196 X번 블록이 넘어지면 Y번 블록이 넘어지는 정보가 여러개 주어질 때 도미노를 직접 넘어뜨려야하는 최소 블록 개수를 출력하는 문제이다. 도미노를 직접 넘어뜨려야 한다는 건 결국 다른 도미노에 의해서 넘어지지 않는다는걸 의미하는데 이는 곧 indegree가 0인 정점의 개수다. 또 하나 고려해줘야 하는 경우가 있는데 cycle을 이룰 경우 indegree가 0이지 않지만 누가 먼저 넘어지지 않는 이상 영원히 넘어지지 않는다. 따라서 우리는 방향 그래프에서 SCC를 구해준 후 SCC로 이루어진 그래프에서 indegree가 0인 SCC의 개수를 세어주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839..

방향 그래프에서 어떤 그룹 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는 집합 내에서 정점들이 서로 왕복 가능한 최대 크기의 집합입니다. 다음과 같은 그래프에..

문제: icpc.me/2150 SCC를 구하는 기본 문제이다. 출력을 SCC가 속한 가장 작은 정점의 정점 번호 순으로 출력해야 하므로 정렬이 필요하다. 코사라주 알고리즘을 통하여 구현하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include #include #define MAX_V 10000using namespace std;int v, e, visited[MAX_V + 1], x, y, r;vector scc;vector vt;vector rvt;stack st;bo..