题目见前文: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;
}
04-27 03:15