22027번 - 통신망 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 | 1024 MB | 69 | 12 | 8 | 23.529% |
문제
통신망은 $N$개의 컴퓨터와 $M$개의 회선으로 구성된다. 컴퓨터는 $1$번부터 $N$번까지 번호가 붙어 있다. 하나의 회선은 서로 다른 $2$개의 컴퓨터가 양방향으로 통신할 수 있도록 한다. 통신망의 어떤 두 컴퓨터도 하나 이상의 회선을 이용해서 통신이 가능하면 통신망은 연결되어 있다고 한다. 통신이 불가능한 컴퓨터의 쌍이 존재하는 경우 통신망은 끊어져 있다고 한다.
통신망의 한 회선 $c$의 위험도는 다음과 같이 정의된다.
- 통신망의 각 컴퓨터 $i$에 대해서, 컴퓨터 $i$를 제거했을 때 남은 통신망이 끊어져 있는 경우 컴퓨터 $i$를 위험한 컴퓨터라고 한다.
- 초기 통신망에서 $c$를 제거했을 때, 위험한 컴퓨터의 개수를 $c$의 위험도로 정의한다.
통신망을 입력으로 받아 각 회선의 위험도를 계산하는 프로그램을 작성하라.
입력
첫째 줄에 두 정수 $N$과 $M$이 주어진다. ($2 \le N \le 250\,000$, $1 \le M \le 1\,000\,000$)
다음 $M$개의 줄에는 회선의 정보가 주어진다. $i$번째 줄에는 $x_i$, $y_i$가 있고, $i$번 회선은 $x_i$번 컴퓨터와 $y_i$번 컴퓨터가 회선으로 연결되어 있음을 의미한다. ($1 \le x_i, y_i \le N, x_i \neq y_i$).
출력
$M$개의 줄을 출력한다. $i$번째 줄에는 $i$번 회선의 위험도를 출력한다.
제한
- $2 \le N \le 250\,000$
- $1 \le M \le 1\,000\,000$
- 한 회선은 서로 다른 두 컴퓨터를 연결한다.
- 동일한 쌍의 컴퓨터를 연결하는 회선이 여러 개 있을 수 있다.
- 초기 통신망은 연결되어 있다.
서브태스크 1 (5점)
- $N \le 200$
- $M \le 500$
서브태스크 2 (11점)
- $N \le 1\,000$
- $M \le 2\,500$
서브태스크 3 (7점)
- $N = M$
서브태스크 4 (13점)
- $k \ge 2$개의 서로 다른 컴퓨터 $v_1, v_2, \cdots, v_k$와 $k$개의 서로 다른 회선 $c_1, c_2, \cdots, c_k$에 대해, 회선 $c_i$가 두 컴퓨터 $v_i$, $v_{i+1}$을 연결하고 $(1 \le i \le k-1)$ 회선 $c_k$가 두 컴퓨터 $v_k$, $v_1$을 연결하면, $k$개의 회선 $c_1, c_2, \cdots, c_k$가 하나의 사이클을 이룬다고 하자. 두 사이클이 같다는 것은 각 사이클을 이루는 회선의 집합이 서로 같음을 의미한다. 통신망의 각 회선 $c$에 대해, 회선 $c$을 포함하는 사이클은 최대 한 개 존재한다.
서브태스크 5 (25점)
- $N \le 8\,000$
- $M \le 250\,000$
서브태스크 6 (29점)
- $N \le 100\,000$
- $M \le 250\,000$
서브태스크 7 (10점)
- 추가적인 제약 조건이 없다.
예제 입력 1
5 5 1 5 5 2 2 3 2 4 2 5
예제 출력 1
4 2 4 4 2
출처
Camp > Petrozavodsk Programming Camp > Winter 2022 > Day 2: Grand Prix of Daejeon G번
Olympiad > 국제정보올림피아드 대표학생 선발고사 > 2021 > 1차 선발고사 2번
Contest > Open Cup > 2021/2022 Season > Stage 11: Grand Prix of Daejeon G번
- 문제를 만든 사람: yclock
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호