7982번: 순열 그래프의 연결성 판별

https://www.acmicpc.net/problem/7982


$O(n)$

간단하게 i와 a[i]를 포함하여 사이에 있는 정점과 i는 같은 집합에 있다고 할 수 있다.
그래서 max(1<=j<=x)(ai)와 x가 같을 때, [1,x]와 [x+1,n]는 단절되어 있다.

#include<cstdio>
int n, maxi, cut[1000001], cnt;
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        if (maxi < x) maxi = x;
        if (maxi == i) cut[++cnt] = i;
    }
    printf("%d", cnt);
    for (int i = 1, j = 1; i <= cnt; i++) {
        printf("\n%d ", cut[i] - cut[i - 1]);
        while (j <= cut[i]) printf("%d ", j++);
    }
    return 0;
}