2
我正在使用鄰接列表表示法處理無向圖的雙向測試。用戶輸入節點以及它們連接的內容，每行是一對。例如：Bipartite無向圖測試：轉換爲使用字符串而不是整數檢查節點
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這樣的數字配對，而是像Jane和Frank這樣的名字，按照與前面例子相同的輸入語法：它們之間的單個空白表示配對。仍然在測試節點，如果它們是兩黨的，在搜索中着色它們，將它們添加到矢量中，稍後在它們各自的組中輸出。所有正在改變的是輸入的數據類型。我的努力沒有取得任何進展。
任何幫助將非常感激。我主要是在尋找數據類型的修正，但我會對其中的任何部分提出批評和建議。請給我一些更多的工作。先謝謝你。
編輯：按照kraskevich給我的想法，我想我已經有所瞭解了。但是我遇到了兩個新問題：最後將地圖放回到一起以輸出名稱，而當前算法（不考慮輸入）返回IMPOSSIBLE。
新代碼：只有主要更改，以及更多矢量的額外全局聲明。
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;
}