악성 루프 탐지
실버 III의견: 0
보안 연구원 수아는 소프트웨어 의존성 그래프를 분석하고 있다. 이 그래프는 \(N\)개의 패키지와 \(M\)개의 단방향 의존 관계로 이루어져 있다. 간선 \(u \to v\)는 '패키지 \(u\)가 패키지 \(v\)에 의존한다'를 뜻한다.
패키지 \(X\)가 어떤 경로를 따라 다시 자기 자신에게 도달할 수 있으면, \(X\)는 악성 루프 위에 있다고 한다.
악성 루프 위에 있는 패키지가 몇 개인지 구하여라.
- \(1 \le N \le 100\,000\)
- \(0 \le M \le 200\,000\)
- \(1 \le u, v \le N\), \(u \ne v\)
첫째 줄에 패키지 수 \(N\)과 의존 관계 수 \(M\)이 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 의존 관계 \(u\), \(v\)가 공백으로 구분되어 주어진다 (\(u \ne v\)). 같은 방향의 간선이 두 번 주어지지 않는다.
악성 루프 위에 있는 패키지 수를 출력한다.
5 4
1 2
2 3
3 1
4 5
3
노드 \(1 \to 2 \to 3 \to 1\)이 사이클을 이루므로 이 세 노드가 악성 루프 위에 있다. 노드 \(4\)와 \(5\)는 어떤 사이클에도 속하지 않는다. 따라서 답은 \(3\)이다.
4 3
1 2
2 3
3 4
0
방향 그래프가 단순 경로를 이루므로 사이클이 없다. 답은 \(0\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
악성 루프 탐지
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
악성 루프 탐지