Module: 강하게 연결된 구성 요소 및 그래프 응축


Problem

1 /1


강력하게 연결된 구성 요소 검색

Problem

<사업부> N개의 꼭지점과 M개의 모서리가 있는 유향 그래프가 제공됩니다(1<=N<=20000, 1<=M<=200000). 주어진 그래프의 강하게 연결된 구성 요소를 찾고 그 응축을 위상적으로 정렬합니다.
<사업부>  
<사업부> 입력
<사업부> 그래프는 다음과 같이 입력 파일에 제공됩니다. 첫 번째 줄에는 숫자 N과 M이 포함됩니다. 다음 M 줄 각각에는 가장자리에 대한 설명이 포함됩니다. 1에서 N까지의 정수 2개 — 가장자리 시작 및 끝 번호.
<사업부>  
<사업부> 출력
<사업부> 첫 번째 줄에 숫자 K를 인쇄합니다. — 주어진 그래프에서 강하게 연결된 구성요소의 수. 다음 줄에 N개의 숫자를 인쇄합니다. — 각 정점에 대해 이 정점이 속한 강하게 연결된 구성 요소의 번호를 인쇄합니다. 강하게 연결된 구성 요소는 모든 가장자리에 대해 시작 부분의 강하게 연결된 구성 요소의 수가 끝의 강하게 연결된 구성 요소의 수를 초과하지 않는 방식으로 번호를 매겨야 합니다.

<몸>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

엔터 출력
<사업부> 10 19 <사업부> 14 <사업부> 78 <사업부> 5 10 <사업부> 8 9 <사업부> 96 <사업부> 26 <사업부> 6 2 <사업부> 38 <사업부> 9 2 <사업부> 7 2 <사업부> 97 <사업부> 4 5 <사업부> 36 <사업부> 73 <사업부> 6 7 <사업부> 108 <사업부> 10 1 <사업부> 29 <사업부> 27 <사업부> 2 <사업부> 1 2 2 1 1 2 2 2 2 1