Codeforces #201, Division 2, B : Fixed Points

問題文

http://codeforces.com/contest/347/problem/B

概要

数列の fixed point を a[ i ] = i を満たす箇所と定める。

N 項からなる数列が与えられる。
この数列に対し、二つのインデックスを選んでその二箇所を入れ替える操作を一回までできる。（やらなくてもよい）
結果として得られる数列の fixed point の数の最大値を求めよ。

解法

二箇所を入れ替える操作では、fixed point の数を最大で 2 まで増やせます。
まず、fixed point の数が n 未満のとき、fixed point でない場所を一つ選んで適当な場所と入れ替えることで fixed point を一つ増やすことができます。

2 増える場合は次のようになります。
位置 p にある値を正しい場所に持っていくと考えると、その行き先は a[ a[ p ] ] です。
このとき a[ a[ p ] ] = p が成り立てば、位置 p も fixed point になるので、合わせて 2 増えます。
そのような位置を全探索で探すことで解けます。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	int res = 0;
	REP( i, 0, n )
	{
		res += as[i] == i;
	}

	REP( i, 0, n )
	{		
		if ( as[i] != i && as[ as[i] ] == i )
		{
			cout << res + 2 << endl;
			return 0;
		}
	}

	res += res < n;
	cout << res << endl;

	return 0;
}