POJ 2337 欧拉回路+欧拉路径+判断欧拉回路和路径

2024-05-10 12:08

本文主要是介绍POJ 2337 欧拉回路+欧拉路径+判断欧拉回路和路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

//
//  main.cpp
//  POJ 2337 欧拉路径
//
//  Created by 郑喆君 on 8/7/14.
//  Copyright (c) 2014 itcast. All rights reserved.
//#include<cstdio>
#include<cstring>
#include<iostream>
#include<iomanip>
#include<queue>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int int_max = 0x07777777;
const int int_min = 0x80000000;
int smaller (int a, int b) { return (a > b ? b : a); }
int bigger (int a, int b) { return (a > b ? a : b); }
const int maxn = 100;
struct Edge {int from,to;Edge(int _from, int _to):from(_from),to(_to){}
};
vector<Edge> es;
vector<int> G[maxn];
void addedge (int from, int to){es.push_back(Edge(from, to));G[from].push_back(es.size()-1);
}
int root[1100];
int tot;
vector<int> g[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
void dfs (int u){pre[u] = lowlink[u] = ++dfs_clock;S.push(u);for(int i = 0; i < g[u].size(); i++){int v = g[u][i];if(!pre[v]){dfs(v);lowlink[u] = smaller(lowlink[u], lowlink[v]);}else if(!sccno[v]){lowlink[u] = smaller(lowlink[u], pre[v]);}}if(lowlink[u]==pre[u]){scc_cnt++;while (true) {int x = S.top();S.pop();sccno[x] = scc_cnt;if(x==u) break;}}
}
void find_scc (int nn){dfs_clock = scc_cnt = 0;memset(sccno, 0, sizeof(sccno));memset(pre, 0, sizeof(pre));for(int i = 0; i < nn; i++){if(!pre[i] && g[i].size()) dfs(i);}
}
int compare(const void *a,const void *b)
{return (strcmp((const char*)a,(const char*)b));
}
int n;
char ss[1100][25];
int vis[1100];
void dfss(int x, int pre){for(int i = 0; i < G[x].size(); i++){if(!vis[G[x][i]]){vis[G[x][i]] = 1;dfss(es[G[x][i]].to, G[x][i]);}}if(pre!=-1) root[tot++] = pre;
}
int main(int argc, const char * argv[])
{int T;scanf("%d",&T);while(T--){scanf("%d", &n);for(int i = 0; i < maxn; i++) g[i].clear();for(int i = 0; i < n; i++) {scanf("%s", ss[i]);g[ss[i][0]-'a'].push_back(ss[i][strlen(ss[i])-1]-'a');g[ss[i][strlen(ss[i])-1]-'a'].push_back(ss[i][0]-'a');}find_scc(26);if(scc_cnt > 1) {cout << "***" << endl; continue;}qsort(ss, n, sizeof(char)*25, compare);es.clear();for(int i = 0; i < maxn; i++) G[i].clear();for(int i = 0; i < n; i++){addedge(ss[i][0]-'a',ss[i][strlen(ss[i])-1]-'a');}int dayu = 0;int xiaoyu = 0;int rudu[26],chudu[26];memset(rudu, 0, sizeof(rudu));memset(chudu, 0, sizeof(chudu));for(int i = 0; i < 26; i++){if(G[i].size()){for(int j = 0; j < G[i].size(); j++){chudu[i]++;rudu[es[G[i][j]].to]++;}}}int flag = 1;for(int i = 0; i < 26; i++){if(abs(rudu[i]-chudu[i]) > 1){flag = 0;break;}if(rudu[i]-chudu[i]==1) dayu++;if(chudu[i]-rudu[i]==1) xiaoyu++;}if(!(flag==1 && ((dayu==1&&xiaoyu==1)||(dayu==0&&xiaoyu==0)))){cout << "***" << endl; continue;}int start = es[0].from;for(int i = 0; i < 26; i++) if(chudu[i]-rudu[i]==1) start = i;memset(vis, 0, sizeof(vis));tot = 0;dfss(start,-1);for(int i = tot-1; i>0; i--) printf("%s.", ss[root[i]]);printf("%s\n", ss[root[0]]);}
}

这篇关于POJ 2337 欧拉回路+欧拉路径+判断欧拉回路和路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/976398

相关文章

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for

如何测试计算机的内存是否存在问题? 判断电脑内存故障的多种方法

《如何测试计算机的内存是否存在问题?判断电脑内存故障的多种方法》内存是电脑中非常重要的组件之一,如果内存出现故障,可能会导致电脑出现各种问题,如蓝屏、死机、程序崩溃等,如何判断内存是否出现故障呢?下... 如果你的电脑是崩溃、冻结还是不稳定,那么它的内存可能有问题。要进行检查,你可以使用Windows 11

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》:本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re