scc

https://www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 문제 풀이 이동 구간 경로가 주어 졌을 때 , 어느쪽을 스타트로 잡아야 하는지 정하는 문제다. 첫 번째 입력을 그래프로 나타내면 다음과 같은데 만약 3번에서 시작한다고 하면 주어진 경로를 모두 탐색할 수 없기 때문에 불가능. 그럼 나머지 0,1,2 번 지점에서는 저 중 아무곳에서 출발을 해도 모든 구간을 탐색이 가능하기 때문에 0,1,2 가 답. 즉 , { 0, 1, 2 } 를 하..

https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net [문제] [풀이] 어우 .. 어질어질하다.. SCC 활용 DP 문제이긴 한데 , 처음에 SCC 집단들을 구해서 indegree가 0인거부터 진행했는데 왜 안되지..? 했다가 나중에 알고보니 start 지점이 정해져있다는 걸 뒤늦게 알았고 한참을 헤맸다 .. 접근방법 1. SCC집단을 구할 것. 2. SCC집단마다 번호를 매기고 , 이 자체를 하나의 Node로 취급하여 또 다른 tot..

https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net [문제] [풀이] x => y => ... 로 가는 간선이 있을 때 , x 를 넘어뜨리면 이와 연결된 모든 도미노가 넘어간다. 즉 , inDegree 가 0인 부분을 선택해서 카운팅 해줘야 하는 문제이다. 그런데 만약 사이클이 있는 경우는 inDegree를 정의하기가 어렵기 때문에 사이클이 있는부분은 어느 하나만 건드리면 나머지도 다 넘어지기 때문에 이 사이클을 하나의 노드로 봐야 한다. 그래서 SCC (강한 결..

https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 문제 풀이 SCC (강한 결합 요소)를 구하기위해 코사라주 알고리즘을 사용했다. 1. 그래프를 dfs 로 탐색하면서 Stack에 탐색한 정점들을 push 2. Stack 에서 원소 하나씩 Pop 하면서 , 역방향 그래프 탐색 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22..