문제

• 본인또는 다른 사람 한명만 선택 가능
• 서로가 서로를 선택하거나 본인을 선택한 경우에만 팀이 됨

풀이

입력 예제

i 1 2 3 4 5 6 7
j 3 1 3 7 3 4 6
v 1 0 1 0 0 0 0
t 0 0 1 0 0 0 0

본인으로부터 시작해서 본인으로 못끝남 (1,3) -> (3,3)
if(i ==j) -> 본인 혼자 팀 (방문함, 팀 형성1으로 갱신)
if(j가 방문 안했고)이고 본인으로 시작해서 본인으로 끝남

21->13->(방문했으므로 못감)33
i 1 2 3 4 5 6 7
j 3 1 3 7 3 4 6
v 1 1 1 0 0 0 0
t 0 0 1 0 0 0 0

47->76->64 (처음과 끝이 같은 경우에 해당 i들의 t를 모두 1로 변경)
i 1 2 3 4 5 6 7
j 3 1 3 7 3 4 6
v 1 1 1 1 0 1 1
t 0 0 1 1 0 1 1

53-> 33(방문했으므로 못감)
i 1 2 3 4 5 6 7
j 3 1 3 7 3 4 6
v 1 1 1 1 1 1 1
t 0 0 1 1 0 1 1

풀이 1

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int board[100001];
int vis[100001][2];

int T, n;
int dx[4] = { 1 , -1, 0, 0 };
int dy[4] = { 0 , 0, 1, -1 };


void print(int n){
    for(int i=1; i<=n; i++){
        cout << i<<' ';
    }
    cout << '\n';
    for(int i=1; i<=n; i++){
        cout<< vis[i][0]<< ' ';
    }
    cout << '\n';
    // for(int i=1; i<=n; i++){
    //     cout<< vis[i][1]<< ' ';
    // }
    cout << "\n\n";
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int count=0;
    
    cin >> T;
    while(T--){
        fill(board, board+100001, 0);
        fill(vis[0], vis[100001],0);
        
        cin >> n;
        for(int i=1; i<=n; i++){
                             //1 2 3 4 5 6 7
            cin >> board[i]; //3 1 3 7 3 4 6
            
            //본인 혼자 팀인 경우
            if(i == board[i]){
                vis[i][0]=1;// 방문으로 바꿈
                //vis[i][1]=1; //팀 여부 1: 팀 형성 0: 팀 형성 x
                count++;
            }
        }
        
        cout << "cnt: "<< count<<'\n';
        
        for(int i=1; i<=n; i++){
            //시작하는 원소 넣기
            queue<pair<int, int>> Q; //47
            Q.push({i,board[i]}); //47
            //현재노드 방문으로 설정
            vis[i][0]=1; //1 1 1 1 0 0 1
            int first = i;//처음 원소 4
            int cnttmp=0; //팀이 되는 개수 0
        
            while(!Q.empty()){ //76
                //print(n);
                auto cur = Q.front(); //76
                Q.pop();

                int next = cur.Y; //6
                //next 거르기:방문했거나 범위를 벗어나면 pass
                if(vis[next][0]==1||next<1||next>n) continue;
                
                if(first == board[next]){//처음과 끝이 같음 1!=3
                    count += cnttmp; //2
                    cout << "cnt: "<<count<<'\n';
                }
                cout << "cnttmp: "<<cnttmp<<' ';
                vis[next][0]=1; //방문으로 변경
                cnttmp++; //1
                Q.push({next, board[next]});  //큐에 다음노드 넣기
                
            }
        }
        
        cout << n-count<<'\n';
        
    }
    
    
    //vis가 0인 원소는 팀에 속하지 못함

    return 0;
}