Qrafın kondensasiyası
Sizə n zirvəsi və m qırağı olan əlaqəli istiqamətli qraf təqdim edilib. Bu qrafın güclü əlaqə komponentlərini müəyyənləşdirin və onun kondensasiyasını topoloji olaraq sıralayın.
Giriş məlumatları
Qraf aşağıdakı şəkildə təqdim olunur: ilk sətir n və m ədədlərini (1 ≤ n ≤ 20000, 1 ≤ m ≤ 200000) ehtiva edir. Sonrakı m sətirin hər biri qırağın təsvirini ehtiva edir - 1-dən n-ə qədər olan iki tam ədəd - qırağın başlanğıc və son nöqtələrinin nömrələri.
Çıxış məlumatları
Birinci sətirdə verilən qrafda güclü əlaqə komponentlərinin sayını çıxarın. Növbəti sətirdə n ədəd çıxarın - hər bir zirvə üçün bu zirvənin aid olduğu güclü əlaqə komponentinin nömrəsini göstərin. Güclü əlaqə komponentləri elə nömrələnməlidir ki, istənilən qıraq üçün başlanğıcının güclü əlaqə komponentinin nömrəsi onun sonunun güclü əlaqə komponentinin nömrəsindən böyük olmasın.