| Submit | All submissions | Best solutions | Back to list |
WEBISL - Web islands |
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 component ID is the smallest page index on the component.
Example
Input: 3 3
0 1
1 0
1 2
Output: 0
0
2
| 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 |
hide comments
|
||||||
|
2015-09-20 14:50:02
getting WA, someone give tough test case |
||||||
|
2015-07-12 17:37:16 Jordan
Using STL gave TLE, even with fast input... |
||||||
|
2015-05-30 09:57:28 Dipti Singhal
need more test cases. getting WA |
||||||
|
2015-03-21 23:46:33 ashish jaiswal
plz explain with other test case..not able to understand. |
||||||
|
2015-03-01 16:19:42 Deepak
Got AC with N = 100005 |
||||||
|
2015-02-07 00:17:25 sanchay
Got A.C assuming N < 10^7. |
||||||
|
2014-11-15 13:39:48 Siya
What is the range of N? |
||||||
|
2014-07-16 11:02:47 Ivan ©ego
@[Lakshman] No. Correct output is: 0 0 0 3 |
||||||
|
2014-07-12 07:54:10 [Lakshman]
Need Help is answer for below case:: 4 4 0 1 1 0 1 2 2 0 ans:: 0 0 0 0 |
||||||
|
2014-04-19 16:34:16 Min_25
@kishlay This problem asks for the strongly connected components of the web pages. On the i-th (0-indexed) line, we need to print the smallest page index on the component which contains page i. Last edit: 2014-06-24 19:56:10 |
||||||
RSS