14076번 - 선인장 선물 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 512 MB | 11 | 5 | 5 | 45.455% |
문제
오늘은 승현이의 생일이다.
석환이는 생일 선물로 승현이에게 선인장 그래프를 선물했다.
선인장 그래프는 N개의 정점과 M개의 간선으로 이루어진 그래프로, 모든 간선이 많아야 하나의 단순 사이클에 속한다는 성질을 가지고 있다. 시작점과 끝점을 제외하고, 경로 상에 속한 모든 정점이 서로 다른 경로를 단순 사이클이라 부른다. 정점의 집합이 같은 단순 사이클은 하나의 단순 사이클로 생각한다. 일반적으로 선인장 그래프는 연결 그래프로 정의되지만, 이 문제에서는 그렇지 않아도 된다.
승현이는 생일 선물로 선인장 그래프를 받은 것이 너무 기쁜 나머지, 현관문을 잠그지 않고 잠들어 버렸다. 이 소식을 들은 도둑 재현이는 승현이의 집에 쳐들어가서 선인장 그래프를 훔쳤다.
재현이가 승현이의 생일 선물을 훔쳐온 이유는 무엇일까? 바로 여러분들에게 문제를 내기 위해서이다. 여러분들은 입력으로 재현이가 훔쳐온 선인장 그래프를 받아서, 해당 그래프의 길이 i (1 ≤ i ≤ N) 의 단순 경로의 개수를 모두 세야 한다. 경로 상에 속한 모든 정점이 서로 다른 경로를 단순 경로라 정의하며, 단순 경로의 길이는, 단순 경로에 속한 정점의 개수로 정의된다.
승현이는 재현이를 경찰에 신고했고, 재현이는 감옥에 가게 되었다. 불쌍한 재현이를 생각해서라도, 빨리 이 문제를 풀어주자.
입력
첫 번째 줄에 선인장의 정점의 수 N, 간선의 수 M이 주어진다. (1 ≤ N ≤ 4000, 0 ≤ M ≤ 100 000)
이후 M개의 줄에 서로 다른 P개의 간선이 주어진다. (1 ≤ x < y ≤ N)
출력
N개의 줄에 길이 i의 단순 경로의 수를 1000000007로 나눈 나머지를 출력하라.
예제 입력 1
3 2 1 2 2 3
예제 출력 1
3 4 2
예제 입력 2
3 3 1 3 2 3 1 2
예제 출력 2
3 6 6
힌트
1번 예제에서,
길이 1의 단순 경로 : {1}, {2}, {3}
길이 2의 단순 경로 : {1, 2}, {2, 3}, {2, 1}, {3, 2}
길이 3의 단순 경로 : {1, 2, 3}, {3, 2, 1}
출처
ICPC > Regionals > Europe > Central European Regional Contest > The Croatian Programming Contest > CPC 2015 D번
- 문제를 번역한 사람: koosaga
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호