Посчитайте, сколько разных векторов осталось после объединения

Question

Посчитайте, сколько разных векторов осталось после объединения

Я использую только std :: vector в этой задаче, и каждый вектор упорядочен без дубликатов. Теперь я хочу объединить векторы с одинаковыми номерами. Таким образом, 2 3 может быть объединением с 3 4 5, но не с 4 5 или 1 5.

Пример:

Если у меня есть следующие векторы …

После объединения у меня осталось только 2 вектора:

1 5
2 3 4 7

коды:

vector<int> a,b,c,d,e,f,g;
vector<vector<int>> myList;

a.push_back(1);
b.push_back(1);
c.push_back(2);
c.push_back(3);
c.push_back(4);
d.push_back(5);
e.push_back(1);
e.push_back(5);
f.push_back(2);
g.push_back(4);
g.push_back(7);

myList.push_back(a);
myList.push_back(b);
myList.push_back(c);
myList.push_back(d);
myList.push_back(e);
myList.push_back(f);
myList.push_back(g);

//this should print out the vectors in my above example
for (int i =0; i<myList.size(); i++) {
for (int j=0; j<myList[i].size(); j++) {
cout<<myList[i][j]<<" ";
}
cout<<endl;
}

Я пытался использовать set_union и set_intersection для достижения своей цели, но он не работает должным образом. Я подозреваю, что проблема заключается в размере вектора, который я не изменяю должным образом. Пожалуйста помоги. Спасибо!

РЕДАКТИРОВАТЬ:

Это ошибочный код, изначально у меня были проблемы с объединением, но только сейчас он работает автоматически .. Теперь я думаю, что я в основном не уверен, как использовать set_intersection, чтобы выяснить, есть ли пересечение

vector<int>::iterator myIt;
vector<int> myTemp;
vector<int> myTemp2;
vector<int> myResult(20);
vector<int> myResult2(20);while (!myList.empty()) {

myTemp2 = myList.back();
myList.pop_back();myIt = set_intersection(myTemp.begin(), myTemp.end(),
myTemp2.begin(), myTemp2.end(), myResult.begin());

//this is checking whether there is intersection but it doesn't work
if (myResult.size()) {

myIt = set_union(myTemp.begin(), myTemp.end(),
myTemp2.begin(), myTemp2.end(), myResult2.begin());

myTemp = myResult2;

}}

cout<<"after union: "<<endl;

for (auto it = myResult2.begin(); it != myResult2.end() ; it++) {
cout<<*it<< " ";
}

0

algorithm c++c++11 stdvector union-find

Решение

Другие решения

Это не идеально

vector<int> myResult(20);

myIt = set_intersection(myTemp.begin(), myTemp.end(),
myTemp2.begin(), myTemp2.end(), myResult.begin());

Проблема в том, что set_intersection (и set_union) не изменяют размер вектора. Делая myResult размером 20, вы даете себе достаточно места, но после пересечения вы все равно получаете вектор размером 20, так что myResult.size() == 20 любые элементы, которые у вас есть в двух векторах для начала.

Вам нужен способ использовать set_intersection, чтобы он добавлял элементы к целевому вектору. Для этого вам нужно back_inserter

#include <iterator>

vector<int> myResult;

set_intersection(myTemp.begin(), myTemp.end(),
myTemp2.begin(), myTemp2.end(),
back_inserter(myResult));

back_inserter добавляет элементы в вектор, используя push_backТаким образом, myResult начинается с нулевого размера и заканчивается в правильном размере, в зависимости от того, сколько элементов находится на пересечении. Итак, вы можете просто проверить myResult.size() > 0 сказать, был ли какой-либо общий элемент.

Сделайте то же самое, когда вызываете set_union.

1

Источник

Accepted Answer

Если я вас правильно понимаю, не только ваш код, но и ваш подход в корне неверен. Вы пытаетесь решить проблему типа связанных компонентов / непересекающихся множеств, но ваш метод, например, возвращает только один vector из ints …? Нужно вернуть vector из vector<int>конечно.

Следующий код — самая близкая к вам, я думаю, которая должна работать. Должно выйти result с выходом, который вы хотите.

vector< vector<int> > result;

for(int i = 0; i < myList.size(); i++)
{

bool match = false;
int matchFirst = -1;

for(int j = 0; j < result.size(); j++)
{

vector<int> myResult;
vector<int> myResult2;

set_intersection(myList[i].begin(), myList[i].end(),
result[j].begin(), result[j].end(),
back_inserter(myResult));

if (myResult.size())
{
set_union(myList[i].begin(), myList[i].end(),
result[j].begin(), result[j].end(), back_inserter(myResult2));

if(match)
{
vector<int> myResult3;
set_union(myResult2.begin(), myResult2.end(),
result[matchFirst].begin(), result[matchFirst].end(), back_inserter(myResult3));
result.erase(result.begin() + j, result.begin() + j + 1);
result[matchFirst] = myResult3;
j--;
}
else
{
matchFirst = j;
result[j] = myResult2;
match = true;
}

}

}

if(!match)
{
result.push_back(myList[i]);
}
}

редактировать: Исправлена ошибка.

1