Euler loop refers to a loop that can draw each side of the picture only once without leaving the pen off the paper, and can return to the starting point. Now let's give a graph and ask whether there is an Euler loop?

Input
The test input contains several test cases. The first line of each test case gives two positive integers, which are the number of nodes N (1 < N < 1000) and the number of edges M; The subsequent M lines correspond to M edges, and each line gives a pair of positive integers, which are the numbers of the two nodes directly connected to the edge (nodes are numbered from 1 to N). Enter knot when N is 0
Bundle.

Output
The output of each test case occupies one line. If Euler loop exists, it will output 1, otherwise it will output 0.

What is Euler loop?
A graph, n points, m edges (edges may be directed, undirected, or a mixture of the two). This title is undirected edge, and the other two are not mentioned
No matter which point you start from, as long as you just finish m edges, each edge here can only pass once, and finally just return to the starting point

Idea:
Solution 1 DFS search
Solution 2 Joint search set + clever method

Solution 1:
If any one of the n points cannot return to the starting point through m edges (edges do not repeat), there must be no Euler circuit in this figure
Analysis: (write down) draw a curve at will from a point (the curve can cross), and finally connect to the starting point.
After the graph is built, you can find a point in the graph at will, and you can return to the origin after passing through all the curves

Solution 2:
1. Judge whether the graph has been connected by using and searching the set. Euler circuit can exist only when it is connected
2. Then for each point, the number of adjacent edges of the point must be even, because after passing through each point, you must go out from the point and try to find more pictures, which is not easy to say

Solution 1:

#include <stdio.h>
#include <string.h>
#define N 1005
int map[N][N];//Save map 
int book[N][N];//Mark the side you pass 
int n,m,flag;
void dfs(int x,int num)
{//x is the entry point of 1 edge, and num indicates that this is standing on the first edge 
	if(flag)
		return;
	if(num==m&&book[x][1]==0&&map[x][1]==1)//Walk on the m side & & there is a way & & haven't walked 
	{
		flag=1;
		return;
	}
	int i;
	for(i=1;i<=n;i++)
	{
		if(map[x][i]==1&&book[x][i]==0)
		{
			book[x][i]=book[i][x]=1;
			dfs(i,num+1);
		}
	}
}
int main()
{
	while(~scanf("%d",&n)&&n)
	{
		memset(map,0,sizeof(map));
		memset(book,0,sizeof(book));
		flag=0;
		int i;
		scanf("%d",&m);
		for(i=1;i<=m;i++)
		{
			int a,b;
			scanf("%d %d",&a,&b);
			map[a][b]=1;
			map[b][a]=1;
		}
		dfs(1,1);
		if(flag)
			printf("1\n");
		else
			printf("0\n");
	}
	return 0;
} 

Solution 2: joint search set + clever thinking

#include<stdio.h>
#include<string.h>
#define N 1010
int f[N];
int dbs[N];//Store the number of adjacent edges of each point 
int cnt,n;
void init()
{
	int i;
	for(i=1;i<=n;i++)
		f[i]=i;
}
int find(int x)//Search the set and find the root node 
{
	if(x!=f[x])
		f[x]=find(f[x]);//Path compression makes it faster to find ancestors 
	return f[x];
}
void merge(int u,int v)
{
	int tu,tv;
	tu=find(u);
	tv=find(v);
	if(tu!=tv)//Inequality indicates that an edge needs to be established. When establishing (n-1) edges, this path has been completely connected 
	{
		f[tv]=tu;
		cnt--;	
	} 
}
int main()
{
	while(~scanf("%d",&n)&&n)
	{
		memset(dbs,0,sizeof(dbs));
		init();
		cnt=n-1;//Whether a graph is connected with, and the number of edges is at least (n-1) 
		int m;
		scanf("%d",&m);
		while(m--)
		{
			int a,b;
			scanf("%d %d",&a,&b);
			dbs[a]++;
			dbs[b]++;
			merge(a,b);
		}
		if(cnt!=0)
		{
			printf("0\n");
			continue;
		}
		int flag=1,i;
		for(i=1;i<=n;i++)
		{
			if(dbs[i]%2)
			{
				flag=0;
				break;
			}
		}
		if(flag)
			printf("1\n");
		else
			printf("0\n");
	}
	return 0;
}