핵심 아이디어

<aside> 💡

함수형 그래프다.

indgree가 0인 곳에서 시작하는 것이 이득이다.

</aside>

다음과 같이 DFS를 실행하면 된다.

• $1$번을 시작으로 DFS를 돌린다. (시작점이 $1$번이므로)
• 아직 방문되지 않은 정점들 중 indgree가 0인 정점들을 시작으로 DFS를 돌린다.
• 아직 방문되지 않은 정점들을 시작으로 DFS를 돌린다.

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long int ll;

int n;
vector<int> adj[100'001];
int idg[100'001];

vector<int> ans;

bool v[100'001];

void dfs(int cur)
{
    v[cur] = true;

    for(int nxt: adj[cur]){
        ans.push_back(nxt);
        if(v[nxt]) continue;
        dfs(nxt);
    }
}

signed main()
{
    FASTIO;
    cin >> n;
    for(int i = 1; i<=n; i++){
        int e;
        cin >> e;
        adj[i].push_back(e);
        idg[e]++;
    }

    dfs(1);
    for(int i = 1; i<=n; i++){
        if(v[i] || idg[i]) continue;
        ans.push_back(i);
        dfs(i);
    }

    for(int i = 1; i<=n; i++){
        if(v[i]) continue;
        ans.push_back(i);
        dfs(i);
    }

    cout << ans.size() <<"\\n";
    for(int e: ans) cout << e <<" ";

    return 0;
}