WEBISL - Web islands

no tags 

For a given set of web pages, we want to find largest subsets such that from every page in a subset you can follow links to any other page in the same subset.

Input

On the first line, there are two numbers, number of the pages N, and total number of links M. Pages are numbered from 0 up to N-1. On lines 2 up to M+1, there are two numbers per line. The first is the source page and the second is the target page of a link.

Output

On N lines there is a component ID for every single page. The componet ID is the smallest page index on the component.

Example

Input:
3 3
0 1
1 0
1 2

Output: 0
0
2

hide comments
islingr: 2019-08-14 19:01:08

By binary searching with initial values of l = 10^4 and r = 10^5 I found that the maximum value of n in the problem is 97032. XD

Last edit: 2019-08-14 22:30:00
dewa251202: 2018-09-30 20:42:34

I'm using Kosaraju, and vectors, why it gives me WA?

anirudnits: 2018-08-01 21:37:43

scc+dsu :)

noobsaibot: 2018-01-24 06:50:18

Please consider memory constraints even though not mentioned in statement, cost me 4 WA and 2 NZEC :( but finally AC ... B-)

luckynarang123: 2018-01-23 14:38:11

will int adj_mat[10001][10001];
will this work or there is any size limit to N ?
It is giving WA, pls help

luckynarang123: 2018-01-23 14:37:14

will adjaceny matrix of size
int adj_mat[10001][10001];

will do ?

mrigank9: 2017-05-02 20:28:44

good question for scc beginners

deerishi: 2016-06-23 05:20:56

AC ONE GO! Cool application of Strongly connected components.

kejriwal: 2015-12-22 21:15:54

AC one go.. also 100th :D

visionvrp: 2015-09-26 04:42:06

AC in one go... hurrray.. :)


Added by:dRak
Date:2013-03-04
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64