08.15后台美团笔试第三题小思路

#include <bits/stdc++.h>
using namespace std;

const int Max = 10000 + 10;
int n,m;
int pre[Max],People[Max];

int find(int x){
	while(x != pre[x])
		x = pre[x];
	return x;
}
void Union(int x,int y){
	x = find(x);
	y = find(y);
	if(x!=y)
		pre[y] = x;
}

int main(){
    cin >> n >> m;
	int a,b;
	for(int i = 1; i <= n; i++)
		pre[i] = i;
	while(m--){
		cin >> a >> b;
        Union(a,b);
	}
	for(int i = 1; i <= n; i++)
		People[i] = 0;
	int k;
	map<int, vector<int>> res;
	for(int i = 1; i <= n; i++){
		k = find(i);
		res[k].push_back(i);
	}
	cout << res.size() << endl;
	map<int, vector<int> >::iterator iter = res.begin();
	vector<vector<int> > t;
	while(iter != res.end()) {
        vector<int> v = iter->second;
        vector<int> temp;
        for(int i = 0; i < v.size(); i++){
            temp.push_back(v[i]);
        }
        t.push_back(temp);
        iter++;
    }
    sort(t.begin(), t.end());

	for (vector<vector<int>>::iterator it = t.begin(); it != t.end(); ++it){
		for (int i = 0; i < (*it).size(); ++i)
			cout << (*it)[i] << " ";
        cout << endl;
	}
    return 0;
}