一笔画问题，，也就是欧拉道路，这一题，简单的欧拉回路的应用。
什么是欧拉回路？
欧拉回路就是在图A中，存在一条路径使得每一条边都走过一次，并且这条路径是一个圈，就是欧拉回路。
欧拉回路的判断：
1.在有向图中：首先必要的条件是图连通，所以顶点的入度都等于出度。
2.在无向图中：首要条件还是图连通，其次就是所以顶点都是偶数度（该顶点的度为偶数）
这一题，还需要加上一个条件，也就是存在两个奇数度的点的情况，也是符合的，从一个奇数点出发，另外一个奇数点结束。
判断图是否连通，可以运用DFS或者并查集，都是很简单的。
下面是dfs的算法：
void dfs(int x){int i;vis[x] = 1;//标记已返问过for(i = 1; i <= n; i++)if(map[x][i]){degree[x]++; //该点度+1if(vis[i] == 0) //没返问过，递归dfs(i);}}下面是AC的代码，我用的是并查集来判连通：
#include <iostream>#include <cstring>using namespace std;const int MAX_N = 1005;int par[MAX_N], degree[MAX_N], n, v;int finds(int x){if(x == par[x])return x;elsereturn par[x] = finds(par[x]);}int main(){//freopen("data.txt", "r", stdin);int t, a, b, i, j;cin >> t;while(t–){cin >> n >> v;memset(degree, 0, sizeof(degree));for(j = 0; j <= n; j++)//初始化并查集par[j] = j;for(i = 0; i < v; i++){cin >> a >> b;degree[a]++; degree[b]++;//该点度+1int next_a = finds(a);int next_b = finds(b);if(next_a != next_b)//合并par[next_a] = next_b;}int flag = 0, tag = 0;for(i = 1; i <= n; i++)//判连通if(par[i] == i)flag++;if(flag > 1)//不连通cout << "No" << endl;else//连通{for(i = 1; i <= n; i++)//判奇数点if(degree[i] % 2)tag++;if(tag == 0 || tag == 2)cout << "Yes" << endl;elsecout << "No" << endl;}}return 0;}
如你想要拥有完美无暇的友谊，可能一辈子找不到朋友
