题解 | #欧拉回路#

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int g[N][N];
int n, m;
//深搜 + 回溯剪枝
bool dfs(int start, int i, int cnt)
{
    if(i == start && cnt == m) return true;
  	bool ret = false;
    for(int j = 1; j <= n && !ret; j ++)
    {
        if(g[i][j])
        {
            g[i][j] = g[j][i] = 0;
            ret |= dfs(start, j, cnt + 1);
            g[i][j] = g[j][i] = 1;    
        }
    }
    return ret;
}
int main() {
    while(cin >> n >> m && n)
    {
        memset(g, 0, sizeof g);
        int i, j;
        for(int k = 0; k < m; k ++)
        {
            cin >> i >> j;
            g[i][j] = g[j][i] = 1;
        }
        bool ret = false;
        for(int k = 1; k <= n && !ret; k ++)
        {
            ret |= dfs(k, k, 0); 
        }
        if(ret) cout << 1 << endl;
        else cout << 0 << endl;
     }

}
// 64 位输出请用 printf("%lld")