hdu 1878オーラ戻り路

構想:この問題は図欧に道を引き返す2つの条件がないことを考察する.条件が満たされているかどうかを直接検証すればいい.

#include <iostream>             
#include <stdio.h>             
#include <cmath>             
#include <algorithm>             
#include <iomanip>             
#include <cstdlib>             
#include <string>             
#include <memory.h>             
#include <vector>             
#include <queue>             
#include <stack>             
#include <map>           
#include <set>           
#include <ctype.h>
#define ll long long         
#define max3(a,b,c) max(a,max(b,c)) 
using namespace std;    

int deg[1010];
bool vis[1010];
vector<int> mp[1010];

int main(){
	int n,m;
	while(cin>>n){
		memset(vis,0,sizeof(vis));
		memset(deg,0,sizeof(deg));
		memset(mp,0,sizeof(mp));
		
		if(!n)break;
		cin>>m;
		for(int i=1;i<=m;i++){
			int u,v;
			cin>>u>>v;
			deg[u]++;
			deg[v]++;
			mp[u].push_back(v);
			mp[v].push_back(u);
		}
		bool ok=1;
		int cnt=0;
		for(int i=1;i<=n;i++){
			if(deg[i]&1){
				cnt++;
			}
		}
		if(cnt>0)ok=0;
		
		queue<int> que; que.push(1);
		vis[1]=1;
		while(!que.empty()){
			int cur=que.front(); que.pop();
			int siz=mp[cur].size();
			for(int i=0;i<siz;i++){
				int v=mp[cur][i];
				if(vis[v])continue;
				vis[v]=1;
				que.push(v);
			}
		}
		for(int i=1;i<=n;i++)if(!vis[i])ok=0;
		
		if(ok){
			cout<<1<<endl;
		}else{
			cout<<0<<endl;
		}
		
	}
	return 0;
}