首页 > 技术文章 > M - 小希的迷宫

liuxin13 2015-07-23 12:35 原文

跟N题是一样的,不过会爆栈,有两种解决办法,第一种加
#pragma comment(linker, "/STACK:102400000,102400000")
这一行代码,不过只能用c++提交,第二种自己写个栈
/////////////////////////////////////
#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<queue>
using namespace std;

const int maxn = 100005;

int f[maxn], use[maxn];

void Init()
{
    for(int i=0; i<maxn; i++)
        f[i] = i, use[i] = 0;
}
int Find(int x)
{
    if(f[x] != x)
        f[x] = Find(f[x]);
    return f[x];
}

int main()
{
    int u, v, ok=1;

    Init();
    while(scanf("%d%d", &u, &v), u!= -1 || v!=-1)
    {
        if(u+v == 0)
        {
            int sum = 0;

            for(int i=0; i<maxn; i++)
            {
                if(use[i] == 1 && f[i] == i)
                    sum++;
            }

            if(ok && sum < 2)printf("Yes\n");
            else printf("No\n");

            ok = 1;
            Init();
        }
        else
        {
            use[u] = use[v] = 1;
            
            u = Find(u);
            v = Find(v);
            
            if(u != v)
                f[u] = v;
            else ok = 0;
        }
    }

    return 0;

} 

推荐阅读