測資生成器

#include <iostream>
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
int arr[50005], N = 50000;

int main(){
    srand(time(NULL));
    freopen("10.in","w",stdout);

    printf("%d\n",N);
    for ( int i = 0 ; i < N ; i++ )
        arr[i] = i;
    random_shuffle( arr, arr+N );

    for ( int i = 0 ; i < N ; i++ ){
        if ( i != 0 )
            putchar( ' ' ); 
        printf("%d",arr[i]);
    }

    printf("\n");



    return 0;    
}

解答

#include <iostream>
#include <math.h>
#include <string.h>
#include <stdio.h>

int p[50005], N;
bool app[50005];


int find_p( int x ){
    return x == p[x] ? x : p[x] = find_p( p[x] );    
}

int main(){
    freopen("10.in","r",stdin);
    freopen("10.out","w",stdout);
    int x, ans = 0;

    scanf("%d",&N);

    for ( int i = 0 ; i < N ; i++ )
        p[i] = i;

    for ( int i = 0 ; i < N ; i++ ){
        scanf("%d",&x);    
        int fa = find_p( i );
        int fb = find_p( x );
        p[ fa ] = fb;
    }


    for ( int i = 0 ; i < N ; i++ ){
        int father = find_p( i );
        if ( !app[father] )
            ans++;
        app[father] = true;
    }

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



    return 0;    
}