请问这道题该怎么做呀,有什么思路?
如果能写出来代码就更好了,谢谢
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
bool vis[111];
int g[111][111];
bool dfs(int s, int t)
{
vis[s] = 1;
if (s == t) return 1;
for (int u = 0; u < N; ++u)
{
if (!g[s][u] || vis[u]) continue;
if (dfs(u, t)) return 1;
}
return 0;
}
bool cyc(int u)
{
bool res;
for (int v = 0; v < N; ++v)
{
if (!g[u][v]) continue;
g[u][v]--; g[v][u]--;
memset(vis, 0, sizeof(vis));
res = dfs(u, v);
g[u][v]++; g[v][u]++;
if (res) return 1;
}
return 0;
}
bool hmr(int u)
{
memset(vis, 0, sizeof(vis));
if (!dfs(0, u)) return 0;
int x = g[0][u];
g[0][u] = g[u][0] = 0;
memset(vis, 0, sizeof(vis));
if (x&1 || dfs(0, u))
{
g[0][u] = g[u][0] = x;
return 1;
}
bool res = cyc(0)||cyc(u);
g[0][u] = g[u][0] = x;
return res;
}
int main()
{
int i, j, k, u, v;
cin >> N >> M;
while (M--)
{
cin >> u >> v;
u--; v--;
g[u][v]++; g[v][u]++;
}
bool mdk = 1;
for (u = 1; u<N && mdk; ++u)
if (g[0][u]) mdk = 0;
int syk = 0;
for (u = 1; u<N && !mdk; ++u)
{
if (!g[0][u]) continue;
int x = g[0][u];
if ((x&1)==0)
{
mdk = 1;
break;
}
g[0][u] = g[u][0] = 0;
memset(vis, 0, sizeof(vis));
if (dfs(0, u))
{
g[0][u] = g[u][0] = x;
mdk = 1;
break;
}
if (x>1 && cyc(u)) mdk = 1;
g[0][u] = g[u][0] = x;
if (x>1) syk++;
}
mdk |= (syk>=2);
if (mdk) cout<<"1 ";
for (u = 1; u < N; ++u)
if (hmr(u)) printf("%d ", u+1);
cout << endl;
return 0;
}