on
[C++]백준 - 3977번 문제
[C++]백준 - 3977번 문제
3977번: 축구 전술 (acmicpc.net)
3977번 : 축구 전술
World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A, B)로 표현한다. 모든 도현이의 팀 선수들이 이 움직임만을 따라서 이동한다면 승리하리라고 도현이는 확신한다.
도현이는 선수들에게 자신의 전술을 말해주며, 다른 모든 구역에 도달할 수 있는 시작 구역을 찾은 뒤 지시한 움직임만을 따라가라고 했다. 그러나 도현이는 한 가지 간과한 것이 있었는데 그건 선수들이 자신만큼 똑똑하지 않다는 것이다. 선수들은 그러한 시작 구역을 찾는 것이 어려웠다. 이제 당신이 적절한 시작 구역을 찾아줘야 한다.
입력
첫 번째 줄에 테스트 케이스의 개수가 주어지며, 이는 11보다 작거나 같은 정수이다.
그 다음 줄부터 여러 개의 테스트 케이스가 주어지는데, 각 테스트 케이스마다 첫 번째 줄에 구역의 수 N, 지시한 움직임의 수 M이 주어지며 1 ≤ N, M ≤ 100,000 이다. 그 다음 M개의 줄에 걸쳐서 움직임 (A, B)가 주어지며, A, B는 0 ≤ A, B < N인 정수이다.
각 테스트 케이스는 하나의 빈 줄로 구분된다.
출력
각 테스트 케이스마다 가능한 모든 시작 구역을 오름차순으로 한 줄에 하나씩 출력한다. 만약 그러한 시작 구역이 없으면, "Confused"를 출력한다.
각 테스트 케이스의 끝에는 하나의 빈 줄을 출력한다.
생각해 볼 점
사실상 4196번 문제와 풀이가 완전히 똑같기 때문에
풀이는 생략하겠습니다.
코드
#include #include #include #include using namespace std; //코사라주 알고리즘의 스택을 채우는 DFS void dfs(bool *&visited;, vector * const &edges;, stack & st, int const current) { if (visited[current]) return; visited[current] = true; for (int next : edges[current]) { dfs(visited, edges, st, next); } st.push(current); } //역방향 에지를 받아 SCC를 판정하는 DFS void dfs(bool*& visited, vector* const& edges, vector &ans;, int const current) { if (visited[current]) return; visited[current] = true; ans.push_back(current); for (int next : edges[current]) dfs(visited, edges, ans, next); } int main() { int T; scanf("%d", &T;); while (T--) { int N, M; scanf("%d %d", &N;, &M;); int* scc_index = new int[N]; //i번째 노드가 몇번 SCC에 속해있는지 저장 bool* visited = new bool[N]; vector* edges = new vector[N]; vector* rev_edges = new vector[N]; for (int i = 0; i < M; i++) { int a, b; scanf("%d %d", &a;, &b;); edges[a].push_back(b); rev_edges[b].push_back(a); } //코사라주 알고리즘 stack st; fill_n(visited, N, false); for (int i = 0; i < N; i++) { if (visited[i]) continue; dfs(visited, edges, st, i); } vector> scc; fill_n(visited, N, false); while (!st.empty()) { int current = st.top(); st.pop(); if (visited[current]) continue; int idx = scc.size(); scc.push_back(vector()); dfs(visited, rev_edges, scc[idx], current); sort(scc[idx].begin(), scc[idx].end()); for (int member : scc[idx]) scc_index[member] = idx; } int const scc_size = scc.size(); int* indegree = new int[scc_size]; fill_n(indegree, scc_size, 0); //SCC 그래프를 위상 정렬, indegree 배열 채우기 for (int i = 0; i < N; i++) { for (int e : edges[i]) { if (scc_index[i] != scc_index[e]) indegree[scc_index[e]]++; } } bool is_possible = false; int ans_index = -1; //진입 에지가 0개인 SCC의 갯수에 따라 판정 for (int i = 0; i < scc_size; i++) { if (indegree[i] == 0) { if (ans_index == -1) { ans_index = i; is_possible = true; } else { is_possible = false; break; } } } if (is_possible) { for (int area : scc[ans_index]) printf("%d
", area); } else printf("Confused
"); printf("
"); delete[] indegree; delete[] edges; delete[] rev_edges; delete[] visited; } return 0; }
그 외
from http://popoli31.tistory.com/213 by ccl(A) rewrite - 2021-12-30 18:26:41