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.


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.


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


3 3
0 1
1 0
1 2

Output: 0

hide comments
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.. :)

ankitrohilla: 2015-09-20 14:50:02

getting WA, someone give tough test case

Jordan: 2015-07-12 17:37:16

Using STL gave TLE, even with fast input...

Dipti Singhal: 2015-05-30 09:57:28

need more test cases. getting WA

ashish jaiswal: 2015-03-21 23:46:33

plz explain with other test case..not able to understand.

Deepak: 2015-03-01 16:19:42

Got AC with N = 100005

sanchay: 2015-02-07 00:17:25

Got A.C assuming N < 10^7.

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