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

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

 

순열 그래프는 N개의 정점이 1 ~ N의 번호가 하나씩 구성되어 있습니다.

그리고 두 정점 쌍 i, j (1 ≤ i < j ≤ n) 는 ai > aj 일때 간선으로 연결되어 있습니다.

4
2 3 1 4

순열이 이렇게 주어졌을 때  2, 3 > 1이므로 (1, 2), (1, 3)이 각각 연결되어 있고

(1, 2, 3) (4) 로 집합을 나눌 수 있습니다.

 

여기서 알 수 있는건 i번째 까지 순회했을때 max가 i이면 해당 위치까지 하나의 집합으로 묶을 수 있습니다.

위의 예시로 보면

3번 인덱스까지의 max가 3이므로 1, 2, 3을 집합으로 묶을 수 있고, 4번 인덱스까지의 max가 4이므로 4를 집합으로 묶을 수 있습니다.

이전 집합의 max값을 유지해주면서 배열을 순회하면 정답을 구할 수 있습니다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1000001
using namespace std;
 
vector<int> v;
int list[MAX];
int N;
 
void func() {
    int maxValue = 0;
    for (int i = 1; i <= N; i++) {
        maxValue = max(maxValue, list[i]);
        if (i == maxValue) v.push_back(i);
    }
 
    int pre = 0;
    cout << v.size() << '\n';
    for (auto x : v) {
        cout << x - pre << ' ';
        for (int i = pre + 1; i <= x; i++) cout << i << ' ';
        cout << '\n';
        pre = x;
    }
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}