AOJ_2217
左上から右下にかけて順番にたどっていき、何個のループがあるか数える。
一度通った場所には印をつけ、ループになっているか確かめながらたどっていくとよい。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100; int N; typedef pair<int, int> P; P map[MAX_N + 2][MAX_N + 2]; //移動先を記憶 int table[MAX_N + 2][MAX_N + 2]; //たどってきた道を書いておく int loop_n = 0; //ループの個数 void find_lp(int x, int y, int a){ if(table[x][y] == a + 1){ //ループとして追加 loop_n++; return; }else if(table[x][y] != 0){ //既にとおったことがある if(table[x][y] == a){ //二周目する table[x][y]++; find_lp(map[x][y].first, map[x][y].second, a); } return; } //通ったことがない table[x][y] = a; find_lp(map[x][y].first, map[x][y].second, a); return; } void init(int a){ //ループの場所以外をきれいにする for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(table[j][i] == a) table[j][i] = 0; } } return; } int main(){ while(scanf("%d", &N)){ if(N == 0) return 0; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ scanf("%d %d", &map[j][i].first, &map[j][i].second); table[j][i] = 0; } } int a = 1; loop_n = 0; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ find_lp(j, i, a); init(a); a += 2; } } printf("%d\n", loop_n); } return 0; }