9466 텀 프로젝트

문제 링크

• 나의 풀이

DFS로 이동하며 발자취를 남겨(vector에 push_back)

흔적을 만날때 까지 반복하다가 흔적이 있는 지점을 만나면

시작한 지점부터 탐색을 다시탐색하며 꼬리 지점이 가리킨 지점까지 찾아간다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int s[100001], chks[100001];
int T, n;

int solve()
{
    int ret = 0;
    int team_num = 0;
    memset(chks, 0, sizeof(chks));
    for (int i = 1; i <= n; i++)
    {
        if (chks[i])
            continue;
        int idx = i;
        team_num += 1;
        chks[i] = team_num;
        vector<int> team;
        team.push_back(i);
        while (true)
        {
            int tg = s[team.back()];

            if (chks[tg])
            {
                if (chks[tg] == team_num)
                {
                    for (int tm : team)
                    {
                        if (tg == tm)
                            break;
                        ret += 1;
                    }
                }
                else
                    ret += team.size();
                break;
            }
            else
            {
                chks[tg] = team_num;
                team.push_back(tg);
            }
        }
    }
    return ret;
}

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

    cin >> T;

    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> s[i];

        cout << solve() << "\n";
    }
}

• 개선된 풀이

vector를 사용하지 않고 풀 수 있다.

#include <cstdio>

char buf[1<<17];

inline char read()
{
    static int idx = 1<<17;
    if (idx == 1<<17)
    {
        fread(buf, 1, 1<<17, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int readInt()
{
    int sum = 0;
    char now = read();
    
    while (now == 10 || now == 32) now = read();
    while (now >= 48 && now <= 57)
    {
        sum = sum*10 + now-48;
        now = read();
    }
    
    return sum;
}
int main()
{
    int t = readInt();
    
    while (t--)
    {
        int n = readInt();
        
        int L[n+1];
        for (int i = 1; i <= n; ++i) L[i] = readInt();
        
        bool visited[n+1]{};
        int ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (visited[i]) continue;
            
            int v = i;
            while (!visited[v])
            {
                visited[v] = 1;
                v = L[v];
            }
            
            int w = i;
            while (w != v)
            {
                ans++;
                w = L[w];
            }
        }
        
        printf("%d\n", ans);
    }
    
    return 0;
}