【算法】Butterfly-BFS

Butterfly

总时间限制: 1000ms 单个测试点时间限制: 100ms 内存限制: 65536kB
描述
有一群旅行爱好者，有一天，他们带回了n只蝴蝶回来。他们相信每一只都属于两个不同种类中的一种，为了讨论方便，我们称它们为A与B。他们想把n只标本分成两组——一些属于A且一些属于B——但是直接标记任何一个标本对于他们是非常困难，因此他们决定采用下面的方法。

对每对标本i和j，他们细心地把它们放到一起研究。如果他们以自己的判断足以确信，那么他们把这对蝴蝶标记为“相同”（这意味着他们相信这两只来自同一类）或者是“不同”（这意味着他们相信这两只来自不同的类）。他们也可以对某些标本判断不出来而弃权，在这种情况下，我们称这对标本是不明确的。

现在他们有n只标本的集合，还有对那些没有弃权的标本对的m个判断的集合（“相同”或者“不同”）。他们想知道这个数据与每只蝴蝶来自A和B中的一个类的想法是否一致。更具体地说，如果对每对蝴蝶按照下述方式标记A或B是可能的，即对每个标为“相同”的（i，j）对，就是i与j有相同标记的情况；对每个标为“不同”的（i，j）对，就是i与j有不同标记的情况。那么我们可以说这m个判断是一致的。他们正在冥思苦想自己的判断是否是一致的。请你帮他们设计合理的算法解决该问题。

输入
输入包含多组数据，以文件结束符为终止。

每组数据第一行为两个整数，分别是n和m：
n为蝴蝶的数量，编号从0到n-1
m为关系的数量

接下来是m组关系数据，每组数据占一行，为三个整数，前两个整数表示蝴蝶的编号，第三个整数为关系的种类（相同或者不同）：
0为相同，1为不同

1 < n <= 1000
1 < m <= 100000
输出
合理就输出YES
不合理就输出NO
样例输入
3 3
0 1 0
1 2 1
0 2 1
3 3
0 1 0
1 2 1
0 2 0
样例输出
YES
NO
提示
注意输出的大写和回车

#include<iostream>
#include<utility>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<unordered_map>

using namespace std;

class butterfly {
public:
	char b_class;
	vector<pair<int, int>> edges;
};

vector<butterfly*> butterflys;
unordered_map<butterfly*, int> visited;

// 创建一个包含n个蝴蝶的vector
void generate_butterflys(int n);
void bfs(butterfly*);
void filledge(int, int, int);

int main() {
	int n1;
	while (cin >> n1) {
		vector<vector<int>> edgeS;
		int yon = 0;
		int n = n1; // n只蝴蝶
		int m; // m条判断
		cin >> m;
		generate_butterflys(n);
		for (int i = 0; i < m; ++i) {
			int point1, point2, deter;
			cin >> point1; cin >> point2; cin >> deter;
			vector<int> temp;
			temp.push_back(point1); temp.push_back(point2); temp.push_back(deter);
			edgeS.push_back(temp);
			temp.clear();
			filledge(point1, point2, deter);
		}
		for (int i = 0; i < n; ++i) {
			if (!visited[butterflys[i]]) {
				bfs(butterflys[i]);
			}
		}
		for (auto i = edgeS.begin(); i < edgeS.end(); ++i) {
			vector<int> c = *i;
			int p1 = c[0];
			int p2 = c[1];
			int det = c[2];
			if (det == 0) {
				if (butterflys[p1]->b_class != butterflys[p2]->b_class) {
					cout << "NO" << endl;
					yon = 1;
					break;
				}
			}
			else {
				if (butterflys[p1]->b_class == butterflys[p2]->b_class) {
					cout << "NO" << endl;
					yon = 1;
					break;
				}
			}
		}
		if (!yon) {
			cout << "YES" << endl;
		}
		visited.clear();
		butterflys.clear(); // 注意是否需要清空每一只蝴蝶
	}
	system("pause");
	return 0;
}

void generate_butterflys(int n) {
	for (int i = 0; i < n; ++i) {
		butterfly* node = new butterfly();
		butterflys.push_back(node);
		visited[node] = 0;
	}
}

void bfs(butterfly* curr) {
	queue<butterfly*> Q;
	curr->b_class = 'A'; // 将第一个点记为A类
	Q.push(curr);
	visited[curr] = 1;
	while (!Q.empty()) {
		butterfly* Vnow = Q.front();
		Q.pop();
		if (!Vnow->edges.empty()) { // 如果这个点有边，则遍历相连的点
			for (vector<pair<int, int>>::iterator p = Vnow->edges.begin(); p < Vnow->edges.end(); ++p) {
				int point = (*p).first;
				int deter = (*p).second;
				if (visited[butterflys[point]] == 0) { // 判断是否已经访问过，没有则继续
					if (deter == 0) { // 如果相同，则标记一样的类别
						if (Vnow->b_class == 'A') {
							butterflys[point]->b_class = 'A';
						}
						else {
							butterflys[point]->b_class = 'B';
						}
					}
					else { // 否则，标记相反的类别
						if (Vnow->b_class == 'A') {
							butterflys[point]->b_class = 'B';
						}
						else {
							butterflys[point]->b_class = 'A';
						}
					}
					Q.push(butterflys[point]);
					visited[butterflys[point]] = 1;
				}
			}
		}
	}
	return;
}

void filledge(int point1, int point2, int deter) {
	butterflys[point1]->edges.push_back(make_pair(point2, deter));
	butterflys[point2]->edges.push_back(make_pair(point1, deter));
}