Codeforces 844C(DFS)

Codeforces 844C
题意：给你一个序列，这个是序列是乱序的，你需要把它给排序，你有k个桶，每个数放入桶以后就会自动排序，然后再把这些数按原来的位置按现在的顺序放入，使得这个序列变得有序。问最大的k为多少？

先对原数组进行离散化，然后就得到一个1到$n$的排列。每个数要排到相应为位置(即$i=a[i]$)，那么我们逐位DFS，每次DFS到该位上的数值。因为$i$位置上的数$a[i]$是要被操作到$a[i]$位置上的，所以这次选的桶必须要选择$a[i]$。然后到了$a[i]$位置按照此过程继续走，直到之后走到的位置之前走过，就能停止了，这时只需要输出所有经过的节点就行，用set存比较好，自动拍好了序。由于操作次数要第一行输出，所以要用$n$个vector存答案，具体看代码的实现。

Codeforces Submission

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int n, a[MAXN], tmp[MAXN], vis[MAXN], ans;
vector<int> step[MAXN];
set<int> s;
void dfs(int u) {
    if (vis[a[u]] == -1) return ;
    //DFS到该位上的数值a[u]
    if (vis[a[u]] == 0) s.insert(a[u]), vis[a[u]] = 1, dfs(a[u]); else {
        step[++ans].push_back(s.size());
        for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
            step[ans].push_back(*it), vis[*it] = -1;
        }
        s.clear(); 
    }
}
void clean() {
    ans = 0, ms(vis, 0);
}
void solve() {
    clean();
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), tmp[i] = a[i];
    sort(tmp + 1, tmp + 1 + n);
    int nx = unique(tmp + 1, tmp + 1 + n) - tmp - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(tmp + 1, tmp + 1 + nx, a[i]) - tmp;
    for (int i = 1; i <= n; i++) dfs(i);
    printf("%d\n", ans);
    for (int i = 1; i <= ans; i++) {
        for (int j = 0; j < (int)step[i].size(); j++) {
            printf("%d ", step[i][j]);
        }
        printf("\n");
    }
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}