欧拉路径:在一个图中,从i点出发,能将每个边遍历一次最终达到j点的一条路径
欧拉回路:i=j时的欧拉路径
欧拉回路:在无向图中,只要每个点的度数均为偶数,那么必定存在欧拉回路。因为每个点的度是偶数,意味着总有成对的入边和出边,则不会出现卡在一个节点的情况。
欧拉路径:有且仅有两个点的度数为奇数,那么存在从其中一个点到另一个点的欧拉路径。
欧拉回路:所有点的入度等于出度,就存在一条欧拉回路。类似于无向图,每个节点都有成对的入边和出边,那么必定存在欧拉回路
欧拉路径:至多一个点的出度 = 入度 + 1 (起点) , 之多一个点的 入度 = 出度 + 1 (终点) 。
至此判断一个图是否存在欧拉回路和欧拉路径已经可以完成。
接下来是知道存在的条件下找出路径。也就是常规的dfs把每条边走一遍。但是注意,第一个栈底的是无路可走的节点,我们在按照栈输出就行,也就是逆序输出,原因如下:
例如 1 - > 2 -> (3 -> 2 ) -> 1 这是个存在环的回路, 但是也满足欧拉路径的要求。
我们在dfs时可以看做每条边都有概率执行, 因此我们会得到这个dfs序: 1 -> 2 -> 1 (然后回溯返回到2) -> 3 - > 2。 顺序输出的话,把一些行不通的路径也输出了 。逆序输出则保证了栈底的必须是第一个无路可走的节点,也就是终点。
// 有可能两个点之间存在多条边,那么可以用vis[x][i] -- ,减一次走一次 void dfs(int x) { for(int i=0; i v);//存储路径上的边 cnt++; } } ans.push(x);//存储路径上的点 }
例如(1,2)(2,4),两个珠子的接触部分颜色相同都为2。当然,因为珠子最后是连成环的,第一个珠子和最后一个珠子也会接触,也要买满足这个条件
先输入T,有T组数据
输入n,有n个珠子
下面n行每行两个数字表示这个珠子的两个颜色,然后问你能不能连成一条链,能的话输出任意一种连接情况即可,不能的话输出失败.
给定的珠子上的两个颜色,看出无向图两个点连上一条边。题目转化成无向图的欧拉回路是否存在,存在即输出。
#include#include using namespace std; vector G[100]; int vis[100][100]; int d[100]; void dfs(int x) { for(int i=0; i 0) { vis[x][v]--; vis[v][x]--; dfs(G[x][i]); printf("%d %d\n",v,x); } } } int main() { int n,m; scanf("%d%d",&n,&m); while(m--) { int a,b; cin>>a>>b; G[a].push_back(b); d[a]++; d[b]++; vis[a][b] ++; vis[b][a] ++; } for(int i=1; i<=n; i++) if(d[i]%2) { puts("some beads may be lost\n"); return 0; } dfs(1); return 0; }