题目见前文:DS实验题 Old_Driver UnionFindSet结构
这里使用邻接表存储敌人之间的关系,邻接表用指针实现:
//
// main.cpp
// Old_Driver3
//
// Created by wasdns on 16/12/18.
// Copyright © 2016年 wasdns. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge
{
edge *next;
int num;
//int len;
}eg[105];
struct head
{
edge *next;
int num;
}h[105];
void IniList(int n)
{
int i;
for (i = 1; i <= n; i++)
{
h[i].next = NULL;
h[i].num = i;
}
}
void CreatList(int x, int y)
{
edge *p1, *p2;
p1 = new edge;
p1 -> next = NULL;
p1 -> num = y;
p2 = new edge;
p2 -> next = NULL;
p2 -> num = x;
//p2 -> len = leng;
edge *p3, *p4;
p3 = h[x].next;
if (p3 == NULL) {
h[x].next = p1;
}
else
{
while (p3 -> next != NULL) {
p3 = p3 -> next;
}
p3 -> next = p1;
}
p4 = h[y].next;
if (p4 == NULL) {
h[y].next = p2;
}
else
{
while (p4 -> next != NULL) {
p4 = p4 -> next;
}
p4 -> next = p2;
}
}
bool isAnamy(int x, int y)
{
bool flag = false;
edge* p = new edge;
p = h[x].next;
while (p != NULL)
{
if (p -> num == y)
{
flag = true;
break;
}
p = p -> next;
}
return flag;
}
int fa[105];
void IniFUS(int n)
{
int i;
for (i = 1; i <= n; i++)
{
fa[i] = i;
}
}
int Find(int x)
{
int f = x;
while (f != fa[f])
{
f = fa[f];
}
int i = x, j;
while (i != f)
{
j = fa[i];
fa[i] = f;
i = j;
}
return f;
}
void Union(int x, int y)
{
int xfa = Find(x);
int yfa = Find(y);
if (xfa != yfa) {
fa[yfa] = xfa;
}
}
void Query(int k)
{
int i;
int x, y;
for (i = 1; i <= k; i++)
{
cin >> x >> y;
if (!isAnamy(x, y))
{
if (Find(x) == Find(y)) {
cout << "Good job" << endl;
}
else {
cout << "No problem" << endl;
}
}
else
{
if (Find(x) == Find(y)) {
cout << "OK but..." << endl;
}
else {
cout << "No way" << endl;
}
}
}
}
int main()
{
int n, m, k;
cin >> n >> m >> k;
IniFUS(n);
IniList(n);
int i, x, y, z;
for (i = 1; i <= m; i++)
{
cin >> x >> y >> z;
if (z == 1) Union(x, y);
else if (z == -1)
{
CreatList(x, y);
CreatList(y, x);
}
}
Query(k);
return 0;
}