# 朝田诗乃 的博客

### 题解 P2307 【迷宫】

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

1、边数不等于点数-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];

{
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;
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;
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");
}
}