题目见前文：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;

}

2016/12/18