CodeChef : Permutation Cycles (PCYCLE)



// http://www.codechef.com/problems/PCYCLE/
// Runtime : 0.00s
// Memory : 2.6M

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

int a [1000 + 5];
bool vis [1000 + 5];
vector <int> v [1000 + 5];
int in = 0;

void traverse (int s)
{
    while ( !vis [s] ) {
        v [in].push_back (s);
        vis [s] = true;
        s = a [s];
    }

    v [in].push_back (s);
    in++;
}

int main ()
{
    int n;
    scanf ("%d", &n);

    for ( int i = 1; i <= n; i++ ) scanf ("%d", &a [i]);

    memset (vis, false, sizeof (vis));

    for ( int i = 1; i <= n; i++ ) if ( !vis [i] ) traverse (i);

    printf ("%d\n", in);

    for ( int i = 0; i < in; i++ ) {
        printf ("%d", v [i] [0]);
        for ( unsigned int j = 1; j < v [i].size (); j++ ) printf (" %d", v [i] [j]);
        printf ("\n");
    }

	return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s