HDU - 1272 小希的迷宫【并查集】

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1272

思路

只需要判断这张图无环并且只有一个连通块就可以了

要注意如果只输入 0 0 那给的是空图要给出 Yes

判断无环有两个方法

0.在并查集的合并操作中如果 find(x) == find(y) 就说明 x 和 y 已经有一条边了再加就是成环了直接 flag = 0

1.我们可以对边的个数计数只有边数== 结点个数-1 才是满足条件的

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a, b) memset(a, (b), sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = acos(-1.0);

const double E = exp(1.0);

const double eps = 1e-30;

const int INF = 0x3f3f3f3f;

const int maxn = 1e5 + 10;

const int MOD = 1e9 + 7;

int pre[maxn];

int find(int x)

{

    int r = x;

    while (pre[r] != r)

        r = pre[r];

    int i = x, j;

    while (i != r)

    {

        j = pre[i];

        pre[i] = r;

        i = j;

    }

    return r;

}

void join(int x, int y)

{

    int fx = find(x), fy = find(y);

    if (x != fy)

        pre[fx] = fy;

}

void init()

{

    for (int i = 0; i < maxn; i++)

        pre[i] = i;

}

int main()

{

    int x, y;

    set <int> s;

    s.clear();

    int edge = 0;

    init();

    while (scanf("%d%d", &x, &y))

    {

        if (x == -1 && y == -1)

            break;

        else if ((x || y))

        {

            edge++;

            s.insert(x);

            s.insert(y);

            join(x, y);

        }

        else

        {

            if (edge == 0)

            {

                printf("Yes\n");

                continue;

            }

            map <int, int> m;

            int len = s.size();

            while (!s.empty())

            {

                int num = find(*s.begin());

                s.erase(s.begin());

                m[num]++;

            }

            int flag = 1;

            if (edge != len - 1 || m.size() != 1)

                flag = 0;

            if (flag)

                printf("Yes\n");

            else

                printf("No\n");

            s.clear();

            edge = 0;

            init();

        }

    }

}

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a, b) memset(a, (b), sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = acos(-1.0);

const double E = exp(1.0);

const double eps = 1e-30;

const int INF = 0x3f3f3f3f;

const int maxn = 1e5 + 10;

const int MOD = 1e9 + 7;

int pre[maxn];

int flag;

int find(int x)      //路径压缩

{

    int r = x;

    while (pre[r] != r)

        r = pre[r];

    int i = x, j;

    while (i != r)

    {

        j = pre[i];

        pre[i] = r;

        i = j;

    }

    return r;

}

//int find(int x)

//{

//  while (x != pre[x])

//      x = pre[x];

//  return x;

//}

void join(int x, int y)

{

    int fx = find(x), fy = find(y);

    if (fx != fy)

        pre[fx] = fy;

    else

        flag = 0;

}

void init()

{

    for (int i = 0; i < maxn; i++)

        pre[i] = i;

}

int main()

{

    int x, y;

    set <int> s;

    s.clear();

    init();

    flag = 1;

    while (scanf("%d%d", &x, &y))

    {

        if (x == -1 && y == -1)

            break;

        else if ((x || y))

        {

            s.insert(x);

            s.insert(y);

            join(x, y);

        }

        else

        {

            if (s.size() == 0)

            {

                printf("Yes\n");

                continue;

            }

            map <int, int> m;

            int len = s.size();

            while (!s.empty())

            {

                int num = find(*s.begin());

                s.erase(s.begin());

                m[num]++;

            }

            if (m.size() != 1)

                flag = 0;

            if (flag)

                printf("Yes\n");

            else

                printf("No\n");

            s.clear();

            init();

            flag = 1;

        }

    }

}

巴特西

HDU - 1272 小希的迷宫【并查集】

最新文章

热门文章

巴特西

HDU - 1272 小希的迷宫 【并查集】

最新文章

热门文章

HDU - 1272 小希的迷宫【并查集】