记录
15:42 2023-5-26
reference:《算法竞赛入门经典第二版》例题6-16
把字母看作结点，单词看成有向边，则问题有解，当且仅当图中有欧拉路径。
有向图欧拉道路(回路)问题，有向图欧拉道路需要基图连通，且度数满足
最多只能有两个点的入度不等于出度，而且必须是其中一个点的出度恰好比入度大1（把它作为起点），另一个的入度比出度大1（把它作为终点）。
判断基图连通的俩种方式:1.dfs 2.并查集
顺便说下，看的时候看了下《算法竞赛进阶指南》，这里面实现图的方式很有意思(哈哈，因为我没接触过，还是要打开思路
int head[N], ver[N], nxt[N], edge[N], tot;
/*
也就是模仿了邻接表的建立
原来的时候
head[x]表示x的第一条边的编号
ver[head[x]]=y
next[head[x]] 表示x的第一条边的下一条边的编号
head[x] -> x第一条边
那么 加入一条新的边就变成了
ver[++tot]=y
edge[tot]=z
next[tot] = head[x] //接管原来的第一条边 或者可以理解为此时next[tot] 和 head[x]指向同一个边
head[x] = tot //更新x的第一条边 也就是断开了原来的第一条边
*/
void add (int x, int y, int z) {
ver[++tot] = y;
edge[tot] = z;
nxt[tot] = head[x];
head[x] = tot;
}
写了这么多，其实需要记住head和next存的都是边的编号，ver数组的下标也是边的编号，这里建图的方式是类似于插头节点建图，所以后面来的边会先访问到。
dfs
#include<cstdio>
#include<iostream>
#include<sstream>
#include<memory.h>
#define MAX_N 100005
using namespace std;
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;
int N;
int T;
int graph[30][30];
int vis[30][30];
int visit[30]; //1表示需要访问的点
int in[30], out[30];
void build_grapch(int v, int u) {
graph[v][u] = 1;
}
void euler(int v) {
for (int i = 0; i < 26; i++) {
if (graph[v][i] && !vis[v][i]) {
vis[v][i] = vis[i][v] = 1;
euler(i);
}
}
}
void dfs(int v) {
visit[v] = 0;
for(int i = 0; i < 26; i++) {
if(graph[v][i] && visit[i]) {
dfs(i);
}
}
}
int main() {
string str;
cin >> T;
// start、end分别表示欧拉路径的起点和终点，startcnt、endcnt表示度数为奇数的点的个数
int start, end, startcnt, endcnt;
// situation 表示欧拉路径的情况，0表示无欧拉路径，1表示有欧拉路径，2表示有欧拉回路
int situation;
while(T--) {
start = end = startcnt = endcnt = 0;
situation = 0;
memset(graph, 0x00, sizeof(graph));
memset(vis, 0x00, sizeof(vis));
memset(visit, 0x00, sizeof(visit));
memset(in, 0x00, sizeof(in));
memset(out, 0x00, sizeof(out));
cin >> N;
for (int i = 0; i < N; i++) {
cin >> str;
int s = str[0] - 'a';
int e = str[str.size() - 1] - 'a';
build_grapch(s, e);
out[s] += 1;
in[e] += 1;
//随便找一个start
start = s;
visit[s] = visit[e] = 1;
}
for(int i = 0; i < 26; i++) {
if(out[i] - in[i] == 1) {
start = i;
startcnt += 1;
} else if(in[i] - out[i] == 1){
end = i;
endcnt += 1;
} else if(in[i] != out[i]) {
startcnt = endcnt = -1; // 有度数为奇数的点，但是不是欧拉路径
}
}
if ((startcnt == 0 && endcnt == 0) || (startcnt == 1 && endcnt == 1)) {
if (startcnt == 1 && endcnt == 1)
situation = 1;
else
situation = 2;
dfs(start);
for(int i = 0; i < 26; i++) {
if(visit[i]) {
situation = 0;
break;
}
}
} else {
situation = 0;
}
if (situation == 0) {
printf("The door cannot be opened.\n");
} else {
printf("Ordering is possible.\n");
}
}
}
并查集
#include<cstdio>
#include<iostream>
#include<sstream>
#include<memory.h>
#define MAX_N 100005
using namespace std;
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;
int N;
int T;
int in[30], out[30];
int is_exist[MAX_N]; //1表示这个字符存在
int par[MAX_N];
int rak[MAX_N];
int find(int x) {
if(par[x] == x) {
return x;
} else {
return par[x] = find(par[x]);
}
}
void init_disjoint_set(int n) {
for(int i = 0; i < n; i++) {
par[i] = i;
rak[i] = 0;
}
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return;
if(rak[x] < rak[y]) {
par[x] = y;
} else {
par[y] = x;
if(rak[x] == rak[y]) rak[x]++;
}
}
int main() {
string str;
cin >> T;
// start、end分别表示欧拉路径的起点和终点，startcnt、endcnt表示度数为奇数的点的个数
int start, end, startcnt, endcnt;
// situation 表示欧拉路径的情况，0表示无欧拉路径，1表示有欧拉路径，2表示有欧拉回路
int situation;
while(T--) {
start = end = startcnt = endcnt = 0;
situation = 0;
memset(in, 0x00, sizeof(in));
memset(out, 0x00, sizeof(out));
memset(is_exist, 0x00, sizeof(is_exist));
init_disjoint_set(26);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> str;
int s = str[0] - 'a';
int e = str[str.size() - 1] - 'a';
unite(s, e);
is_exist[s] = is_exist[e] = 1;
out[s] += 1;
in[e] += 1;
//随便找一个start
start = s;
}
for(int i = 0; i < 26; i++) {
if(out[i] - in[i] == 1) {
start = i;
startcnt += 1;
} else if(in[i] - out[i] == 1){
end = i;
endcnt += 1;
} else if(in[i] != out[i]) {
startcnt = endcnt = -1; // 有度数为奇数的点，但是不是欧拉路径
}
}
if ((startcnt == 0 && endcnt == 0) || (startcnt == 1 && endcnt == 1)) {
if (startcnt == 1 && endcnt == 1)
situation = 1;
else
situation = 2;
//找到第一个字符
int root = find(start);
for(int i = 0; i < 26; i++) {
if(is_exist[i]) {
if(find(i) != root) {
situation = 0;
break;
}
}
}
} else {
situation = 0;
}
if (situation == 0) {
printf("The door cannot be opened.\n");
} else {
printf("Ordering is possible.\n");
}
}
}
利用数组构造邻接表的dps(emm有点拗口)
#include<cstdio>
#include<iostream>
#include<sstream>
#include<memory.h>
#define MAX_N 1000005
using namespace std;
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;
int N;
int T;
int head[30], ver[MAX_N], nxt[MAX_N], total; //邻接表
int visit[30]; //1表示需要访问的点
int in[30], out[30];
void add_edge(int x, int y) {
ver[++total] = y;
nxt[total] = head[x];
head[x] = total;
}
void dfs(int x) {
visit[x] = 0;
for(int e = head[x]; e ; e = nxt[e]) {
int i = ver[e];
if (visit[i]) {
dfs(i);
}
}
}
int main() {
string str;
cin >> T;
// start、end分别表示欧拉路径的起点和终点，startcnt、endcnt表示度数为奇数的点的个数
int start, end, startcnt, endcnt;
// situation 表示欧拉路径的情况，0表示无欧拉路径，1表示有欧拉路径，2表示有欧拉回路
int situation;
while(T--) {
start = end = startcnt = endcnt = 0;
situation = 0;
memset(head, 0x00, sizeof(head));
memset(ver, 0x00, sizeof(ver));
memset(nxt, 0x00, sizeof(nxt));
total = 0;
memset(visit, 0x00, sizeof(visit));
memset(in, 0x00, sizeof(in));
memset(out, 0x00, sizeof(out));
cin >> N;
for (int i = 0; i < N; i++) {
cin >> str;
int s = str[0] - 'a' + 1; //从1开始
int e = str[str.size() - 1] - 'a' + 1;
add_edge(s, e);
out[s] += 1;
in[e] += 1;
//随便找一个start
start = s;
visit[s] = visit[e] = 1;
}
for(int i = 1; i <= 26; i++) {
if(out[i] - in[i] == 1) {
start = i;
startcnt += 1;
} else if(in[i] - out[i] == 1){
end = i;
endcnt += 1;
} else if(in[i] != out[i]) {
startcnt = endcnt = -1; // 有度数为奇数的点，但是不是欧拉路径
}
}
if ((startcnt == 0 && endcnt == 0) || (startcnt == 1 && endcnt == 1)) {
if (startcnt == 1 && endcnt == 1)
situation = 1;
else
situation = 2;
dfs(start);
for(int i = 1; i <= 26; i++) {
if(visit[i]) {
situation = 0;
break;
}
}
} else {
situation = 0;
}
if (situation == 0) {
printf("The door cannot be opened.\n");
} else {
printf("Ordering is possible.\n");
}
}
}