L2-010 排座位

题目 L2-010 排座位

思路分析

找关系——并查集

用rela记录两两间的直接关系

用并查集记录间接关系

struct DSU{
	vector<int> fa;
	DSU(int n){
		fa.resize(n+1);
		for(int i=0;i<=n;i++)
			fa[i]=i;
	}
	int find(int x){
		if(fa[x]!=x)
			fa[x]=find(fa[x]);
		return fa[x];
	}
	void unite(int x,int y){
		int fx=find(x);
		int fy=find(y);
		if(fx!=fy)
			fa[fx]=fy;
	}
	bool connected(int x,int y){
		return find(x)==find(y);
	}
}

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

struct DSU{

	vector<int> fa;

	DSU(int n){

		fa.resize(n+1);

		for(int i=0;i<=n;i++){

			fa[i]=i;

		}

	}

	int find(int x){

		if(fa[x]!=x)

			fa[x]=find(fa[x]);

		return fa[x];

	}

	void unite(int x,int y){

		int fx=find(x);

		int fy=find(y);

		if(fx!=fy)

			fa[fx]=fy;

	}

	bool connected(int x,int y){

		return find(x)==find(y);

	}

};

const int MAXN = 105;

int rela[MAXN][MAXN];

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int N,M,K;cin>>N>>M>>K;

	DSU dsu(N);

	int a,b,c;

	for(int i=1;i<=M;i++){

		cin>>a>>b>>c;

		rela[a][b]=rela[b][a]=c;

		if(c==1)	dsu.unite(a,b);

	}

	for(int i=1;i<=K;i++){

		cin>>a>>b;

		if(rela[a][b]!=-1 && dsu.connected(a,b))	cout<<"No problem"<<endl;

		else if(rela[a][b]==0 && !dsu.connected(a,b))	  cout<<"OK"<<endl;

		else if(rela[a][b]==-1 && dsu.connected(a,b))	cout<<"OK but..."<<endl;

		else if(rela[a][b]==-1 && !dsu.connected(a,b))	cout<<"No way"<<endl;

	}

	return 0;

}

同类题型

视频讲解

⬅️ L2-009 抢红包 🏠 00-天梯赛 ➡️ L2-011 玩转二叉树