Я работаю над двудольным тестом для неориентированных графов, используя представление списка смежности. Пользователь вводит узлы и то, к чему они подключаются, причем каждая линия представляет собой пару. Например:
0 1
2 3
1 2
0 3
означает, что 0 соединен с 1 и 3, 2 связан с 1 и 3 и т. д. Алгоритм выполняет BFS, раскрашивая узлы по мере продвижения и проверяя, может ли он быть двудольным. В дополнение к проверке, является ли граф двудольным, он сохраняет и выводит, какие узлы принадлежат какой группе в отсортированном порядке. Следуя предыдущему примеру, 1 и 3 будут в группе A, 2 и 0 будут в группе B. Пример вывода будет таким:
Group A:
0
2
Group B:
1
3
Насколько я могу судить, текущий алгоритм работает нормально, почти не имеет проблем, сохранив несколько «грязных» битов кода здесь и там, которые можно было бы очистить. Вот вся программа:
#include <iostream>
#include<vector>
#include<queue>
#include<map>
#include<list>
#include<algorithm>
#include<set>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
vector<int>vec[50];
map<int,int>color;
queue<int>q;
vector<int> B;
vector<int> H;
bool check(int n, int src){
q.push(src);
int i;
color[src]=1;
while(!q.empty()){
src = q.front();
q.pop();
for(i=0;i<vec[src].size();i++){
if(color[vec[src][i]]==-1){ //vec[src][i] = data; color[src] = color;
color[vec[src][i]]= 1 - color[src];
q.push(vec[src][i]);
if (color[src] == 0
and find(B.begin(), B.end(), vec[src][i]) == B.end()
and find(H.begin(), H.end(), vec[src][i]) == H.end()){
B.push_back(vec[src][i]); }
else if (color[src] == 1
and find(B.begin(), B.end(), vec[src][i]) == B.end()
and find(H.begin(), H.end(), vec[src][i]) == H.end()){
H.push_back(vec[src][i]); }
}
else if(color[vec[src][i]]== color[src]){
return 0; }
else{
if(find(B.begin(), B.end(), vec[src][i]) != B.end()){
break; }
else if(find(H.begin(), H.end(), vec[src][i]) != H.end()){
break; }
else{ B.push_back(vec[src][i]); }
}
}
}
return 1;
}
int distinct(const vector<int>& v){
set<int> distinct_container;
for(auto curr_int = v.begin(), end = v.end(); curr_int != end; ++curr_int){
distinct_container.insert(*curr_int); }
return distinct_container.size();
}
int main() {
int inp; int index = 0; vector<int> Input;
while (cin >> inp){
Input.push_back(inp); }
int points = distinct(Input);
while(index < points){
color[index]= - 1; index++; }
index = 0;
while(index < Input.size()){
vec[Input[index]].push_back(Input[index + 1]);
vec[Input[index + 1]].push_back(Input[index]);
index += 2;
}
bool res = 1; index = 0;
for(int i = 0; i < points; i++){
if(color[i]==-1){
res = res && check(points, i); }
}
if(res){
sort(B.begin(), B.end());
sort(H.begin(), H.end());
cout << "Group A:\n"; int x = 0;
while (x < B.size()){
cout << B[x] << "\n"; x++; }
cout << "Group B:\n"; int y = 0;
while (y < H.size()){
cout << H[y] << "\n"; y++; }
}
else{
cout << "IMPOSSIBLE"; }
return 0;
}
Теперь проблема, с которой я столкнулся, заключается в том, что мне нужно преобразовать узлы, чтобы они имели строку в качестве данных, а не целое число. Вместо того, чтобы соединять числа, такие как 1 и 2, я хочу соединить имена, такие как Джейн и Фрэнк, следуя тому же синтаксису ввода, что и в предыдущем примере: один пробел между ними указывает на спаривание. Все еще проверяем узлы, если они двухпартийные, раскрашивая их в поиске, добавляя их к векторам для вывода позже в соответствующих группах. Все, что меняется, — это тип данных ввода. И я не добился прогресса в своих попытках.
Любая помощь будет чрезвычайно оценена. Я в основном ищу исправление для типов данных, но я приму критику и рекомендации по любому из них. Пожалуйста, дайте мне что-нибудь еще для работы. Заранее спасибо.
Редактировать: следуя идее, изложенной мне Краскевичем, я думаю, что у меня это получается. Но я столкнулся с двумя новыми проблемами: объединение карт в конце для вывода имен, и текущий алгоритм, независимо от ввода, возвращает НЕВОЗМОЖНО.
Новый код: изменен только основной и дополнительные глобальные объявления большего количества векторов.
map<string, int> toNum;
vector<string> numToString;
vector<int> BN;
vector<int> HN;
vector<string> BS;
vector<string> HS;
................
int main(){
string s; vector<int> Input; int edges = 0;
while (cin >> s){
edges++; }
int id; int index = 0; int points = 0;
if (toNum.find(s) != toNum.end()){
id = toNum[s]; }
else{
numToString.push_back(s);
toNum.insert( pair<int, string>(numToString.size() - 1, s));
id = numToString.size() - 1; ++points;
Input.push_back(id); }
while(index < points){
color[index]= - 1; index++; }
index = 0;
while(index < numToString.size()){
vec[Input[index]].push_back(Input[index + 1]);
vec[Input[index + 1]].push_back(Input[index]);
index += 2;
}
bool res = 1; index = 0;
for(int i = 0; i < points; i++){
if(color[i]==-1){
res = res && check(points, i); }
}
if(res){
index = 0; int key = 0; string name;
while (index < BN.size()){
name = toNum[BN[index]];
BS.push_back(name);
index++; }
index = 0;
while (index < HN.size()){
name = toNum[BN[index]];
HS.push_back(name);
index++; }
sort(BS.begin(), BS.end());
sort(HS.begin(), HS.end());
cout << "GROUP A\n"; int x = 0;
while (x < BS.size()){
cout << BS[x] << "\n"; x++; }
cout << "GROUP B\n"; int y = 0;
while (y < HS.size()){
cout << HS[y] << "\n"; y++; }
}
else{
cout << "IMPOSSIBLE"; }
return 0;
}
