多组数据,每组m+3数据行。第一行有两个数字n,m和k,代表有n个顶点,m条边和长度k。第二行有n个字符,代表n个顶点的编号。第三行到第m+2行每行有两个字符h和p,代表边依附的两个顶点。每条边的长度为1。第m+3行有两个字符d和f,代表需要判断的两个字符。
时间: 2024-02-25 11:57:10 浏览: 71
我们第一行包括两个整数n,k(1<=n<=100,k<=6e5),表示有n个数字,目标和为k 第二行输入n个整数(c1 c2
以下是读入多组数据的完整代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXVEX 100 // 最大顶点数
// 边表结点
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
// 顶点表结点
typedef struct VNode {
char data; // 顶点数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAXVEX];
// 图的邻接表结构
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 根据顶点数据在邻接表中查找顶点的下标
int locateVex(ALGraph G, char v) {
int i;
for (i = 0; i < G.vexnum; i++) {
if (G.vertices[i].data == v) {
return i;
}
}
return -1;
}
// 创建无向图G
int CreateUDG(ALGraph &G, int vexnum, int arcnum, char ch[]) {
int i, j, k;
ArcNode *p;
char v1, v2;
G.vexnum = vexnum;
G.arcnum = arcnum;
// 初始化顶点表
for (i = 0; i < G.vexnum; i++) {
G.vertices[i].data = ch[i];
G.vertices[i].firstarc = NULL;
}
// 构造邻接表
for (k = 0; k < G.arcnum; k++) {
scanf("%c%c", &v1, &v2);
getchar();
i = locateVex(G, v1);
j = locateVex(G, v2);
// 头插法插入边表结点
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
// 由于是无向图,对称地插入边表结点
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = p;
}
return 1;
}
// DFS遍历图,查找是否存在从u到v的路径
int DFS(ALGraph G, int u, int v, int k) {
int w;
ArcNode *p;
if (u == v && k == 0) {
return 1;
}
if (k == 0) {
return 0;
}
for (p = G.vertices[u].firstarc; p != NULL; p = p->nextarc) {
w = p->adjvex;
if (DFS(G, w, v, k - 1)) {
return 1;
}
}
return 0;
}
int main() {
int n, m, k, i, j, flag;
char ch[MAXVEX];
char d, f;
while (scanf("%d%d%d", &n, &m, &k) != EOF) {
getchar();
for (i = 0; i < n; i++) {
scanf("%c", &ch[i]);
getchar();
}
ALGraph G;
CreateUDG(G, n, m, ch);
scanf("%c%c", &d, &f);
getchar();
flag = 0;
for (i = 0; i < n; i++) {
if (ch[i] == d) {
for (j = 0; j < n; j++) {
if (ch[j] == f && DFS(G, i, j, k)) {
flag = 1;
break;
}
}
if (flag) {
break;
}
}
}
if (flag) {
printf("yes\n");
} else {
printf("no\n");
}
}
return 0;
}
```
注意读入顶点编号时需要使用getchar()来读取换行符。同时,需要在读入每个字符后调用getchar()来消耗掉换行符。
阅读全文