UVAOJ10596 | 哈喽哈咯

Written by razrlele 22:18 February 19, 2015

UVAOJ10596

真是跪了。。。明明书上是先讲拓扑后讲欧拉的。。。却先搞这么大一串欧拉的题目，搞得我每次读题都会先各种先发制人想是不是拓扑，完了每次最后发现是欧拉也是醉了。。。

首先这个题是个大坑，目测AC率太低的原因就是近期有改过数据。。。然后网上的解题报告目测都是改数据之前的。。。然后就。。。

题目就是求是否存在欧拉环路（因为那个熊孩子走完了还要走回家，所以只能是欧拉环路），另外！！那个熊孩子走的是roads！不是road intersections！

也就是说在图中只需要走完所有的边就可以了，有点不一定有边相连，所以不是走完所有的点（网上的解题报告都是写的要走完点，交上去清一色WA）。。。

/********************************************************

* File Name: uvaoj10596.cpp

* Author: razrLeLe

* Mail: razrlele@gmail.com

* Homepage: https://yueyu.io

* Created Time: Thu 19 Feb 2015 02:58:25 PM CST

******************************************************/

#include "vector"

#include "set"

#include "deque"

#include "queue"

#include "algorithm"

#include "functional"

#include "iostream"

#include "cstdio"

#include "cmath"

#include "cstdlib"

#include "string"

#include "cstring"

#include "string.h"

#include "map"

#include "cctype"

#include "list"

#include "stack"

using namespace std;

#define INF 0x3f3f3f3f

#define LOCAL

const int maxn = 250;

int grid[maxn][maxn];

int cnt[maxn];

int vis[maxn];

int N, R;

int c1, c2;

bool possible;

void DFS(int a)

{

vis[a] = true;

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

{

if(grid[a][i] && !vis[i])

{

DFS(i);

}

return ;

}

int main()

{

#ifdef LOCAL

freopen("/home/razrlele/build/data.txt", "r", stdin);

freopen("/home/razrlele/build/out.txt", "w", stdout);

#endif

while(~scanf("%d %d", &N, &R))

{

if(R == 0)

{

printf("Not Possible\n");

continue;

}

memset(grid, 0, sizeof(grid));

memset(cnt, 0, sizeof(cnt));

possible = true;

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

{

scanf("%d %d", &c1, &c2);

grid[c1][c2]++;

grid[c2][c1]++;

cnt[c1]++;

cnt[c2]++;

}

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

{

if(cnt[i] % 2)

{

possible = false;

break;

}

if(possible)

{

memset(vis, false, sizeof(vis));

DFS(0);

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

if(!vis[i] && cnt[i])//是他！就是他！

{

possible = false;

break;

}

printf("%s\n", possible?"Possible":"Not Possible");

}

return 0;

}