Codechef -> Practice -> Easy -> PermutationCycles

Problem Link : http://www.codechef.com/problems/PCYCLE

Solution :

import java.io.BufferedInputStream;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.PrintWriter;

import java.util.ArrayList;

/**

 *

 * @author XCoder

 */

class PermutationCycles {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static PrintWriter pw = new PrintWriter(System.out);

    public static int readIntLine() throws IOException {

        return Integer.parseInt(br.readLine());

    }

    public static long readLongLine() throws IOException {

        return Long.parseLong(br.readLine());

    }

    static int a[];

    static int done[];

    public static void main(String[] args) throws IOException {

        int size = readIntLine();

        a = new int[size + 1];

        done = new int[size + 1];

        int positionInA[] = new int[size + 1];

        String str = br.readLine();

        String split[] = str.split(" ");

        for (int i = 1; i <= split.length; i++) {

            int temp = Integer.parseInt(split[i - 1]);

            a[i] = temp;

            positionInA[temp] = i;

        }

        ArrayList<String> output = new ArrayList<String>();

        for (int i = 1; i < done.length; i++) {

            if(done[i]!=1){

                output.add(givePermutCycle(i));

            }

//            output.add(givePermutCycle(i));

//            for (int j = i + 1; j < done.length; j++) {

//                if (done[j] != 1) {

//                    i = j - 1;

//                    break;

//                }

//            }

//            System.out.println(output);

//            for(int x:done){

//                System.out.println(x);

//            }

        }

        pw.println(output.size());

        for (String s : output) {

            pw.println(s);

        }

        pw.flush();

        pw.close();

    }

    public static String givePermutCycle(int startindex) {

        StringBuffer temp = new StringBuffer(startindex + " ");

        done[startindex] = 1;

        int index = startindex;

        int itemp = 0;

        while (itemp != startindex) {

//            temp += a[index] + " ";

            temp.append(a[index]).append(" ");

            itemp = a[index];

            index = a[index];

            done[index] = 1;

        }

        return temp.toString();

    }

}