Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2015-2016‎ > ‎

25. alkalom

Részfeladat volt: irányított gráfban minden pont kimenő fokszáma 1, adjuk meg a leghosszabb irányított kör hosszát.

import java.util.Scanner;
class OLEB {
    static int T;
    static int[] A;
    static int N;
    
    public static void main(String args[]) {
        Scanner be = new Scanner(System.in);
        T = be.nextInt();
        
        for(int t = 1; t <= T; t++) {
            // teszteset beolvasasa
            N = be.nextInt();
            A = new int[N+1];
            for(int j = 1; j <= N; j++) {
                A[j] = be.nextInt();
            }
            
            int MAX = 0;
            int h = 0;
            
            // minden csucsbol keresunk kort
            for(int start = 1; start <= N; start++) {
                int[] volt = new int[N+1];
                volt[start] = 1; h = 1;
                int poz = start;
                while( volt[A[poz]] != 1) {
                    poz = A[poz];
                    h++;
                    volt[poz] = 1;
                }
                if( A[poz] == start && h > MAX) MAX = h;
            }
            System.out.println("Case #"+t+": "+MAX);
            
        }
    }
}

Feladat