北京市保障性住房建设投资中心网站6,网络规划与设计案例,把自己的网站卖给别人后对方做违法吗,wordpress备案号代码在一张图中#xff0c;从一个点出发每条边经过且只经过一次得到的路径#xff0c;如果最后回到起点#xff0c;那么就是欧拉回路#xff0c;如果最后没有回到起点#xff0c;那么得到的就是欧拉路径。
在无向图中#xff0c;欧拉路径满足的要求是#xff0c;除了起点和…在一张图中从一个点出发每条边经过且只经过一次得到的路径如果最后回到起点那么就是欧拉回路如果最后没有回到起点那么得到的就是欧拉路径。
在无向图中欧拉路径满足的要求是除了起点和终点以外其他点的度数都是偶数欧拉回路满足的要求是所有点的度数都是偶数。
在有向图中欧拉路径满足的要求是除了起点和终点外其他点的出度等于入度起点的出度比入度多1终点的入度比出度多1在欧拉回路中所有点的出度等于入度。
通常找欧拉路径的算法就是dfs遍历但是这里的判重是判重边而非判重点。而且是当一个点所有的边都遍历结束后才会将该点算入答案。我们以一个点为例若有m条自环路径那么每条路径出就要开一层一直往下递归。那么时间复杂度就变成m^2,这个时间复杂度很高所有我们由此产生优化遍历一条边那么就把它删掉以防后面再次遍历到这条边产生不必要的冗余。但是这里如果仅仅通过h[u]ne[i]来删除后面遍历时可以生效但是回溯到前面遍历并不是再从开头开始所以并没有生效(或者换个角度来理解我们的删除相当于直接将头节点的指针往后移但是中间节点的指针是没有改变的所以实际上前面的循环应该已经到了中间那么节点的部分它们之间的指向关系并没有改变仍然会产生新的递归循环)时间复杂度还是很高那么该如何处理呢我们这里通过传入指针来实现动态的删除。
void dfs(int u)
{for (int i h[u]; ~i;){if (used[i]){i ne[i];continue;}used[i] true;if (type 1) used[i ^ 1] true;int t;if (type 1){t i / 2 1;if (i 1) t -t;}else t i 1;int j e[i];i ne[i];dfs(j);ans[ cnt] t;}
}
我们在定义的时候定义int ih[u]修改i的时候h[u]也被同步修改了往后递归的时候我们每次都从h[u]开始h[u]不是一成不变的修改i相当于修改h[u]修改h[u]相当于修改中间节点的指向中间节点的指向关系变了那么往前回溯的过程中就不会出现刚刚m^2的问题了。
1123. 铲雪车活动 - AcWing 这里有个很迷惑人的条件铲雪的时候前进速度是20不铲雪的时候前进速度是50但是显然不铲雪的前提是学已经铲过了那么就相当于这条路走了两边当然是只走一遍更划算。每条道路的两个方向均需要铲雪所以每条路径的出度等于入度那么就是欧拉回路所以我们可以保证每条路径只经过一次所以我们统计出所有的路径再除20即可。这里的时间转化我们可以先求出分钟数然后再进行转化。
#includebits/stdc.h
using namespace std;
int s,t;
double getd(double a,double b,double c,double d)
{double dxa-c,dyb-d;double resdx*dxdy*dy;return sqrt(res);
}
int main()
{scanf(%d%d,s,t);double a,b,c,d;double ans0;while(~scanf(%lf%lf%lf%lf,a,b,c,d)){double sdgetd(a,b,c,d);ans 2*sd;}int mround(ans/1000/20*60);int hm/60;m%60;printf(%d:%02d,h,m);}
1184. 欧拉回路(活动 - AcWing) 要注意欧拉回路和欧拉路径中是可以有孤立点的经过所有边不一定经过所有点所以dfs要找一个有出边的点开始遍历/
#includebits/stdc.h
using namespace std;
const int N100010,M400010;
int t,n,m;
int cnt;
int ans[M],used[M];
int h[N],e[M],ne[M],idx;
int din[N],dout[N];
void add(int a,int b)
{e[idx]b,ne[idx]h[a],h[a]idx;
}
void dfs(int u)
{for(int i h[u];~i;){if(used[i]){ine[i];continue;}used[i]1;if(t1) used[i^1]1;int res;if(t1){resi/21;if(i1) res*-1;}else resi1;int je[i];ine[i];dfs(j);ans[cnt]res;}}
int main()
{scanf(%d%d%d,t,n,m);memset(h,-1,sizeof h);for(int i1;im;i){int a,b;scanf(%d%d,a,b);add(a,b);if(t1) add(b,a);din[b],dout[a];}if(t1){for(int i1;in;i){if(din[i]dout[i]1){printf(NO);return 0;}}}else{for(int i1;in;i){if(din[i]!dout[i]){printf(NO);return 0;}}}for(int i1;in;i){if(h[i]!-1){dfs(i);break;}}if(cnt!m) printf(NO\n);else{printf(YES\n);for(int icnt;i1;i--){printf(%d ,ans[i]);}}
} 另外要注意我们dfs求得的路径是从终点到起点的所以输出的时候需要倒着输出。
1124. 骑马修栅栏1124. 骑马修栅栏 - AcWing题库 这里我们需要输出经过的节点同时使得在有多组解的情况下输出节点序最小的那组解。那么我们首先应该找到最小的有出边的点从这里开始遍历另外为了使得后面的点也是小的在前面我们需要先遍历所有出边中连接的点编号最小的出边那么可以用邻接矩阵来存边。
本题不确定是求欧拉回路还是欧拉路径所以我们先找出第一个有边的点然后遍历查找是否有度为奇数点如果有就替换否则就直接搜欧拉回路。
#includebits/stdc.h
using namespace std;
const int N510;
int n;
int g[N][N],ans[N*N],cnt,d[N];
void dfs(int u)
{for(int i1;i500;i){if(g[u][i]){g[u][i]--,g[i][u]--;dfs(i);}}ans[cnt]u;
}
int main()
{scanf(%d,n);for(int i1;in;i){int a,b;scanf(%d%d,a,b);g[a][b],g[b][a];d[a],d[b];}int s1;while(!d[s])s;for(int is;i500;i){if(d[i]%2) {si;break;}}dfs(s);for(int icnt;i1;i--) printf(%d\n,ans[i]);}
1185. 单词游戏活动 - AcWing 思路这里如果将单词视为节点显然建边太麻烦了我们可以用之前的一个思路在一个单词的首尾字母之间建边这样的话就只有26个点实现复杂度一下就降低了。 那么就要想是建有向边还是无向边我们要注意顺序问题所以建的是有向边。然后实际上不用真的去搜只需要判断一下每个点的出度入度是否符合要求然后判断一下边是否连通。这里判断边是否连通不用dfs我们用并查集来判断。
#includebits/stdc.h
using namespace std;
const int N30,M200010;
int st[M];
int dout[N],din[N];
int p[N];
int find(int x)
{if(x!p[x]) p[x]find(p[x]);return p[x];
}
int main()
{int t;scanf(%d,t);while(t--){int n;scanf(%d,n);memset(st,0,sizeof st);memset(din,0,sizeof din);memset(dout,0,sizeof dout);for(int i0;i26;i) p[i]i;for(int i1;in;i){string s;cins;int as[0]-a,bs[s.size()-1]-a;st[a]st[b]1;dout[a],din[b];p[find(a)]find(b);}int flag1,sc0,ec0;for(int i0;i26;i){if(dout[i]-din[i]1) sc;else if(din[i]-dout[i]1) ec;else if(din[i]!dout[i]) {flag0;break;}}if (flag !(!sc !ec || sc 1 ec 1)) flag 0;int rep-1;for(int i0;i26;i){if(st[i]){if(rep-1) repfind(i);else if(rep!find(i)){flag0;break;}}}if(!flag) printf(The door cannot be opened.\n);else printf(Ordering is possible.\n);}
}
这题判断边是否连通也可以用dfs来写只不过时间复杂度太高了会超时这里还是把代码放上。
#includebits/stdc.h
using namespace std;
const int N30,M200010;
int st[M];
int dout[N],din[N];
int p[N];
int h[N],e[M],ne[M],idx;
int used[M];
int cnt;
void add(int a,int b)
{e[idx]b,ne[idx]h[a],h[a]idx;
}
void dfs(int u)
{for (int i h[u]; ~i;){if (used[i]){i ne[i];continue;}used[i] true;int j e[i];i ne[i];dfs(j);cnt;}
}
int main()
{int t;scanf(%d,t);while(t--){int n;scanf(%d,n);memset(used,0,sizeof used);memset(din,0,sizeof din);memset(dout,0,sizeof dout);memset(h,-1,sizeof h);for(int i1;in;i){string s;cins;int as[0]-a,bs[s.size()-1]-a;dout[a],din[b];add(a,b);}int flag1,sc0,ec0;for(int i0;i26;i){if(dout[i]-din[i]1) sc;else if(din[i]-dout[i]1) ec;else if(din[i]!dout[i]) {flag0;break;}}if (flag !(!sc !ec || sc 1 ec 1)) flag 0;if(!flag) printf(The door cannot be opened.\n);//判连通else {int s0;while(!dout[s]) s;for(int i0;i26;i)if(dout[i]-din[i]1){si;break;}dfs(s);if(cntn) printf(The door cannot be opened.\n);else printf(Ordering is possible.\n);}}
}
所以可以见得判断欧拉回路和欧拉路径只要判断度和连通性的性质满足即可方法不唯一。
