朝田诗乃 的博客

朝田诗乃 的博客

题解 P2307 【迷宫】

posted on 2017-09-27 18:31:41 | under 题解 |

好像没有广搜,我来发一个

题意:

1、边数不等于点数-1不可行(要么不连通要么有环)

2、不连通不可行

在输入后判断1条件,若满足则判2,从一点出发若能到达所有点即连通, 否则不连通。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#define MAXN 1000050
using namespace std;

struct Edge
{
    int to, next;
} e[MAXN << 1];

bool ap[MAXN];
int h[MAXN];
int en, dn, edn, st;
bool vis[MAXN];

void addedge(int u, int v)
{
    e[++en].to = v;
    e[en].next = h[u];
    h[u] = en;
}
int main()
{
    while("我是天才")
    {
        en = 0;
        dn = 0;
        edn = 0;
        memset(h, -1, sizeof(h));
        memset(ap, 0, sizeof(ap));
        int u, v;
        scanf("%d%d", &u, &v);
        if(u == -1 || v == -1) break;
        addedge(u, v);
        addedge(v, u);
        edn++;
        if(!ap[u]) dn++;
        if(!ap[v]) dn++;
        ap[u] = 1;
        ap[v] = 1;
        st = u;
        while("我是大帅哥") //不要在意这些细节
        {
            scanf("%d%d", &u, &v);
            if(u == 0 || v == 0) break;
            addedge(u, v);
            addedge(v, u);
            edn++; //计算边的数量
            if(!ap[u]) dn++;
            if(!ap[v]) dn++; //计算点的数量
            ap[u] = 1;
            ap[v] = 1;
        }
        if(edn != dn - 1) //判断条件1
        {
            printf("0\n");
            continue;
        }
        queue <int> q;
        q.push(st);
        int cnt = 0;
        memset(vis, 0, sizeof(vis));
        vis[st] = 1;
        while(!q.empty()) //尝试遍历所有点
        {
            int u = q.front();
            q.pop();
            cnt++;
            for(int i = h[u]; ~i; i = e[i].next)
            {
                int v = e[i].to;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
        if(cnt != dn) printf("0\n"); //有的没到达过
        else printf("1\n");
    }
}