map+并查集 50pts求条
查看原帖
map+并查集 50pts求条
533102
monodev楼主2023/11/25 16:40
#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<int, int> itoi;

struct node {
	int a, b;
	bool e;
} eq[2000001];
int eqtop;

#include <vector>							// 需要用到 STL vector 
class unionfind {
	private:
		int _setcount;
		vector <int> father, size;
		
		int findfather(int n){
			if(this -> father[n] == n)
				return n;
			else 
				return this -> father[n] = findfather(this -> father[n]);
		}
	public:
		void init(int size, int begin = 0){	// 初始化并查集,下标从begin开始,大小为size (note:空复O(size))
			this -> _setcount = size;
			this -> father.clear();
			this -> size.clear();
			for(int i = 0; i < size + begin; i ++){
				this -> father.push_back(i);
				this -> size.push_back(1);
			}
		}
		bool connected(int n, int m){		// 判断n和m是否在一个集合 
			return findfather(n) == findfather(m);
		}
		bool connected(){					// 判断并查集是否联通
			return this -> _setcount == 1;
		}
		void merge(int n, int m){			// 合并n和m所在的集合 
			if(!connected(n, m))
				-- _setcount;
			int nroot = findfather(n);
			int mroot = findfather(m);
			
			if(nroot != mroot){
				if(this -> size[nroot] > this -> size[mroot])
					swap(nroot, mroot);
				this -> father[nroot] = mroot;
				this -> size[mroot] += this -> size[nroot];
			}
		}
		int setcount(){						// 获取并查集的集合总数 
			return this -> _setcount;
		}
} uf;

int main(){
	int T;
	cin >> T;
	while(T--){
		itoi.clear();
		eqtop = 0;
		
		int n;
		cin >> n;
			
		for(int i = 0; i < n; ++ i){
			int a, b;
			bool e;
			cin >> a >> b >> e;
			eq[eqtop].a = a;
			eq[eqtop].b = b;
			eq[eqtop ++].e = e;
			if(itoi.find(a) != itoi.end()) itoi[a] = itoi.size();
			if(itoi.find(b) != itoi.end()) itoi[b] = itoi.size();
		}
		
		uf.init(2 * n, 0);
		for(int i = 0; i < n; ++ i)
			if(eq[i].e)
				uf.merge(itoi[eq[i].a], itoi[eq[i].b]);
		bool flag = false;
		for(int i = 0; i < n; ++ i)
			if(!eq[i].e)
				if(uf.connected(itoi[eq[i].a], itoi[eq[i].b])){
					cout << "NO" << endl;
					flag = true;
					break;
				}
		if(flag)
			continue;
		cout << "YES" << endl;
	}
}
2023/11/25 16:40
加载中...