Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- vector<int> idx, sz;
- int find_root(int A) {
- while(A != idx[A]) {
- idx[A] = idx[idx[A]];
- A = idx[A];
- }
- return A;
- }
- void merge_two_rots(int A, int B) {
- int root_a = find_root(A);
- int root_b = find_root(B);
- if(root_a == root_b) {
- return;
- }
- if(sz[root_a] < sz[root_b]) {
- idx[root_a] = idx[root_b];
- sz[root_b] += sz[root_a];
- }
- else {
- idx[root_b] = idx[root_a];
- sz[root_a] += sz[root_b];
- }
- }
- vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
- int n = accounts.size();
- idx.resize(n);
- sz.resize(n);
- for(int i = 0; i < n; i++) {
- idx[i] = i;
- sz[i] = 1;
- }
- for(int i = 0; i < n; i++) {
- for(int j = 1; j < accounts[i].size(); j++) {
- for(int k = 0; k < n; k++) {
- if(i != k) {
- if(accounts[i][0] == accounts[k][0]) {
- for(int l = 1; l < accounts[k].size(); l++) {
- if(accounts[i][j] == accounts[k][l]) {
- merge_two_rots(i, k);
- break;
- }
- }
- }
- }
- }
- }
- }
- map<int, vector<string>> mapa;
- for(int i = 0; i < n; i++) {
- int root = find_root(i);
- for(int j = 0; j < accounts[i].size(); j++) {
- mapa[root].push_back(accounts[i][j]);
- }
- }
- vector<vector<string>> res;
- for(map<int, vector<string>>::iterator it = mapa.begin(); it != mapa.end(); it++) {
- set<string> st;
- for(int i = 0; i < it->second.size(); i++) {
- if(it->second[i] != it->second[0]) {
- st.insert(it->second[i]);
- }
- }
- vector<string> vv;
- vv.push_back(it->second[0]);
- for(set<string>::iterator it2 = st.begin(); it2 != st.end(); it2++) {
- vv.push_back(*it2);
- }
- res.push_back(vv);
- }
- return res;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement