题目大意:人与人关系可能不一样,给出关系,再给询问两个人什么关系
做法:用并查集做即可,朋友的朋友算一个连通块,不过要注意如果是敌对关系要特殊标记下,代码如下:
/*
coder:sunshine
school:njupt
*/
#include <bits/stdc++.h>
using namespace std;
#define endl "
" //交互题删掉
#define x first
#define y second
typedef long long ll;
typedef pair<int, int> pii;
constexpr int mod = 1e9 + 7;
constexpr int N = 110;
int p[N]; //祖宗数组
int didui[N][N]; //是敌对关系
int n, m, q;
int find(int x) //找祖宗
{
if (x != p[x])
p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y) //圈子融合
{
int a = find(x), b = find(y);
if (a != b)
p[a] = b;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) //初始化并查集
p[i] = i;
for (int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
if (c == -1)
didui[a][b] = didui[b][a] = 1; //表示两个人是敌人
else
merge(a, b); //圈子融合到一起
}
while (q--)
{
int a, b;
cin >> a >> b;
int pa = find(a), pb = find(b);
if (pa == pb && !didui[a][b])
cout << "No problem" << endl;
else if (pa != pb && !didui[a][b])
cout << "OK" << endl;
else if (pa == pb && didui[a][b])
cout << "OK but..." << endl;
else
cout << "No way" << endl;
}
return 0;
}
文章为作者独立观点,不代表股票配资公司观点