PTA-学校-数据结构（图）

1-1 采用邻接矩阵表示法创建无向图

分数 4

作者 王东

单位 贵州师范学院

采用邻接矩阵表示法创建无向图G ，依次输出各顶点的度。

函数接口定义：

void CreateUDN(AMGraph &G);

其中 G 是采用邻接矩阵表示的无向图。

裁判测试程序样例：

#include <stdio.h>
#define MVNum 100                           
typedef struct{ 
    char vexs[MVNum];          
    int arcs[MVNum][MVNum];   
    int vexnum,arcnum;      
}AMGraph;

void CreateUDN(AMGraph &G);
int main(){
    AMGraph G;     
    int i , j,sum=0;
    CreateUDN(G);
    for(i = 0 ; i < G.vexnum ; ++i){
        sum=0;
        for(j = 0; j < G.vexnum; ++j){
            if(G.arcs[i][j]==1)
                sum+=1;
        }
        if(i==0)
            printf("%d",sum);
        else
            printf(" %d",sum);
    }
    return 0;
}

/* 请在这里填写答案 */

输入格式:

输入第一行中给出2个整数i(0<i≤10)，j(j≥0)，分别为图G的顶点数和边数。
输入第二行为顶点的信息，每个顶点只能用一个字符表示。
依次输入j行，每行输入一条边依附的顶点。

输出格式:

依次输出各顶点的度，行末没有最后的空格。

输入样例:

5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE

输出样例:

2 3 3 3 3

解析

void CreateUDN(AMGraph &G) {
    // 1. 读取顶点数和边数
    scanf("%d %d", &G.vexnum, &G.arcnum);
    
    // 2. 读取顶点信息（如ABCDE，存入vexs数组）
    scanf("%s", G.vexs);  // %s读取连续非空白字符，适配顶点无空格输入
    
    // 3. 初始化邻接矩阵：所有元素设为0（0表示无边）
    for (int i = 0; i < G.vexnum; ++i) {
        for (int j = 0; j < G.vexnum; ++j) {
            G.arcs[i][j] = 0;
        }
    }
    
    // 4. 处理每条边，填充邻接矩阵（无向图双向对称）
    char u, v;  // 存储一条边的两个顶点
    for (int k = 0; k < G.arcnum; ++k) {
        // 读取边的两个顶点（加空格跳过前导换行/空格，避免读取错误）
        scanf(" %c%c", &u, &v);
        
        // 找到顶点u和v在vexs数组中的索引（即顶点编号）
        int i = -1, j = -1;
        for (int m = 0; m < G.vexnum; ++m) {
            if (G.vexs[m] == u) i = m;  // 记录u的索引
            if (G.vexs[m] == v) j = m;  // 记录v的索引
            if (i != -1 && j != -1) break;  // 找到两个顶点后提前退出
        }
        
        // 无向图：u→v和v→u都是边，邻接矩阵对称设为1
        G.arcs[i][j] = 1;
        G.arcs[j][i] = 1;
    }
}

1-2 采用邻接表创建无向图

分数 4

作者 王东

单位 贵州师范学院

采用邻接表创建无向图G ，依次输出各顶点的度。

函数接口定义：

void CreateUDG(ALGraph &G);

其中 G 是采用邻接表表示的无向图。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
#define MVNum 100 
typedef struct ArcNode{
    int adjvex; 
    struct ArcNode *nextarc; 
    int info; 
}ArcNode; 

typedef struct VNode{ 
    char data; 
    ArcNode *firstarc; 
}VNode, AdjList[MVNum]; 

typedef struct{ 
    VNode vertices[MVNum]; 
    int vexnum, arcnum; 
}ALGraph;

void CreateUDG(ALGraph &G);

int main(){
    ALGraph G;     
    int i , j,sum=0;
    CreateUDG(G);
    ArcNode * p; 
    for(i = 0 ; i < G.vexnum ; ++i){
        sum=0;
        p=G.vertices[i].firstarc;
        for(; p!=NULL; p=p->nextarc){
                sum+=1;
        }
        if(i==0)
            printf("%d",sum);
        else
            printf(" %d",sum);
    }
    return 0;
}

/* 请在这里填写答案 */

输入格式:

输入第一行中给出2个整数i(0<i≤10)，j(j≥0)，分别为图G的顶点数和边数。
输入第二行为顶点的信息，每个顶点只能用一个字符表示。
依次输入j行，每行输入一条边依附的顶点。

输出格式:

依次输出各顶点的度，行末没有最后的空格。

输入样例:

5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE

输出样例:

2 3 3 3 3

解析

void CreateUDG(ALGraph &G) {
    // 1. 读取顶点数和边数（注意：这里要先读完第一行，避免换行符残留）
    scanf("%d %d", &G.vexnum, &G.arcnum);
    getchar();  // 吸收第一行输入后的换行符，关键！
    
    // 2. 读取顶点信息（第二行是连续字符，用%s读取，自动跳过空白符）
    char vex_str[MVNum];  // 临时存储顶点字符串（如ABCDE）
    scanf("%s", vex_str);
    // 初始化顶点数组：赋值顶点信息，邻接表表头置空
    for (int k = 0; k < G.vexnum; ++k) {
        G.vertices[k].data = vex_str[k];  // 从字符串中逐个取顶点
        G.vertices[k].firstarc = NULL;    // 表头初始为空
    }
    
    // 3. 处理每条边，创建双向边节点
    char u, v;
    for (int k = 0; k < G.arcnum; ++k) {
        // 读取边的两个顶点（%c前加空格，进一步避免残留空白符）
        scanf(" %c%c", &u, &v);
        
        // 3.1 查找u和v对应的顶点索引（加固：确保找到顶点）
        int i = -1, j = -1;
        for (int m = 0; m < G.vexnum; ++m) {
            if (G.vertices[m].data == u) i = m;
            if (G.vertices[m].data == v) j = m;
            if (i != -1 && j != -1) break;
        }
        // 题目保证输入合法，此处可省略检查，但保留逻辑更安全
        if (i == -1 || j == -1) continue;
        
        // 3.2 创建u→v的边节点（头插法）
        ArcNode *p1 = (ArcNode *)malloc(sizeof(ArcNode));
        if (p1 == NULL) exit(1);  // 极端情况：内存分配失败（题目场景下几乎不会触发）
        p1->adjvex = j;
        p1->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p1;
        
        // 3.3 创建v→u的边节点（无向图双向对称）
        ArcNode *p2 = (ArcNode *)malloc(sizeof(ArcNode));
        if (p2 == NULL) exit(1);
        p2->adjvex = i;
        p2->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p2;
    }
}

1-3 基于邻接矩阵表示的广度优先遍历

分数 4

作者 王东

单位 贵州师范学院

实现基于邻接矩阵表示的广度优先遍历。

函数接口定义：

void BFS(Graph G, int v);

其中 G 是基于邻接矩阵存储表示的无向图，v表示遍历起点。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
#define MVNum 10
                        
int visited[MVNum];
typedef struct{ 
    char vexs[MVNum];                    
    int arcs[MVNum][MVNum]; 
    int vexnum,arcnum;             
}Graph;
 
void CreateUDN(Graph &G);//实现细节隐藏
void BFS(Graph G, int v);
void BFSTraverse(Graph G){ 
    int v;
    for(v = 0; v < G.vexnum; ++v)  visited[v] = 0;    
    for(v = 0; v < G.vexnum; ++v)
        if(!visited[v])  BFS(G, v); 
}
int main(){
    Graph G;
    CreateUDN(G);
    BFSTraverse(G);
    return 0;
}


/* 请在这里填写答案 */

输入样例：

输入第1行为结点数vexnum和边数arcnum。第2行为结点的值，依次输入arcnum行，每行输入两个结点的值表示该两个结点互为邻接点。

8 8
ABCDEFGH
A B
A C
B D
B E
C F
C G
D H
E H

输出样例：

遍历序列。

A B C D E F G H 

解析

void BFS(Graph G, int v) {
    int queue[MVNum];  // 用数组实现队列（适配MVNum≤10，无需动态内存）
    int front = 0, rear = 0;  // 队列头、尾指针（front=rear表示队列空）

    // 1. 标记起点v为已访问，输出顶点值
    visited[v] = 1;
    printf("%c ", G.vexs[v]);

    // 2. 起点入队
    queue[rear++] = v;

    // 3. 队列不为空时，循环处理
    while (front < rear) {
        int u = queue[front++];  // 出队当前顶点u

        // 4. 遍历所有顶点，查找u的未访问邻接点
        for (int w = 0; w < G.vexnum; ++w) {
            // 条件：u和w之间有边（arcs[u][w]=1）且w未访问（visited[w]=0）
            if (G.arcs[u][w] == 1 && visited[w] == 0) {
                visited[w] = 1;  // 标记为已访问
                printf("%c ", G.vexs[w]);  // 输出顶点
                queue[rear++] = w;  // 邻接点w入队，等待后续处理
            }
        }
    }
}

1-4 基于邻接表表示的广度优先遍历

分数 4

作者 王东

单位 贵州师范学院

实现基于邻接表表示的广度优先遍历。

函数接口定义：

void BFS(ALGraph G, int v);

其中 G 是基于邻接表存储表示的无向图，v表示遍历起点。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
#define MVNum 10
#define MAXQSIZE 100

bool visited[MVNum]; 
typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextarc;
    int info; 
}ArcNode; 

typedef struct VNode{ 
    char data;
    ArcNode *firstarc;
}VNode, AdjList[MVNum];

typedef struct{ 
    AdjList vertices; 
    int vexnum, arcnum;
}ALGraph;

int CreateUDG(ALGraph &G);//实现细节隐藏
void BFS(ALGraph G, int v);

void BFSTraverse(ALGraph G){ 
 int v;
 for(v = 0; v < G.vexnum; ++v)  
   visited[v] = 0;    
 for(v = 0; v < G.vexnum; ++v)
   if(!visited[v])  
     BFS(G, v);
} 

int main(){
 ALGraph G;
 CreateUDG(G);
 BFSTraverse(G);
 return 0;
}
/* 请在这里填写答案 */

输入样例：

输入第1行为结点数vexnum和边数arcnum。第2行为结点的值，依次输入arcnum行，每行输入两个结点的值表示该两个结点互为邻接点。

8 8
ABCDEFGH
A B
A C
B D
B E
C F
C G
D H
E H

输出样例：

遍历序列。

A C B G F E D H 

解析

void BFS(ALGraph G, int v) {
    int queue[MAXQSIZE];  // 数组实现队列（裁判定义MAXQSIZE=100，足够容纳所有顶点）
    int front = 0, rear = 0;  // 队列头指针（出队）、尾指针（入队）

    // 1. 标记起点v为已访问，输出顶点值，入队缓存
    visited[v] = true;
    printf("%c ", G.vertices[v].data);
    queue[rear++] = v;

    // 2. 队列不为空时，循环处理待访问顶点
    while (front < rear) {
        int u = queue[front++];  // 出队当前顶点u
        ArcNode *p = G.vertices[u].firstarc;  // 拿到u的邻接表表头

        // 3. 遍历u的所有邻接点（沿邻接链表遍历）
        while (p != NULL) {
            int w = p->adjvex;  // 邻接点的索引（顶点编号）
            if (!visited[w]) {  // 邻接点w未访问
                visited[w] = true;  // 标记为已访问
                printf("%c ", G.vertices[w].data);  // 输出顶点
                queue[rear++] = w;  // 邻接点w入队，等待后续处理
            }
            p = p->nextarc;  // 访问下一个邻接点
        }
    }
}

1-5 实现基于邻接表表示的深度优先遍历

分数 4

作者 王东

单位 贵州师范学院

实现基于邻接表表示的深度优先遍历。

函数接口定义：

void DFS(ALGraph G, int v);

其中 G 是基于邻接表存储表示的无向图，v表示遍历起点。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
#define MVNum 10
int visited[MVNum]; 
typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextarc;
    int info; 
}ArcNode; 

typedef struct VNode{ 
    char data;
    ArcNode *firstarc;
}VNode, AdjList[MVNum];

typedef struct{ 
    AdjList vertices; 
    int vexnum, arcnum;
}ALGraph;

int CreateUDG(ALGraph &G);//实现细节隐藏
void DFS(ALGraph G, int v);

void DFSTraverse(ALGraph G){ 
 int v;
 for(v = 0; v < G.vexnum; ++v)  
   visited[v] = 0;    
 for(v = 0; v < G.vexnum; ++v)
   if(!visited[v])  
     DFS(G, v);
} 

int main(){
 ALGraph G;
 CreateUDG(G);
 DFSTraverse(G);
 return 0;
}

/* 请在这里填写答案 */

输入样例：

输入第1行为结点数vexnum和边数arcnum。第2行为结点的值，依次输入arcnum行，每行输入两个结点的值表示该两个结点互为邻接点。

8 8
ABCDEFGH
A B
A C
B D
B E
C F
C G
D H
E H

输出样例：

遍历序列。

A C G F B E H D 

解析

void DFS(ALGraph G, int v) {
    // 1. 标记当前顶点v为已访问，输出顶点值
    visited[v] = 1;
    printf("%c ", G.vertices[v].data);

    // 2. 拿到当前顶点v的邻接表表头，遍历所有邻接点
    ArcNode *p = G.vertices[v].firstarc;
    while (p != NULL) {
        int w = p->adjvex;  // 邻接点的索引（顶点编号）
        if (!visited[w]) {  // 邻接点w未访问，递归深入遍历
            DFS(G, w);
        }
        p = p->nextarc;  // 回溯：遍历下一个邻接点
    }
}

1-6 实现基于邻接矩阵表示的深度优先遍历

分数 4

作者 王东

单位 贵州师范学院

实现基于邻接矩阵表示的深度优先遍历。

函数接口定义：

void DFS(Graph G, int v);

其中 G 是基于邻接矩阵存储表示的无向图，v表示遍历起点。。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
#define MVNum 10
                        
int visited[MVNum];
typedef struct{ 
    char vexs[MVNum];                    
    int arcs[MVNum][MVNum]; 
    int vexnum,arcnum;             
}Graph;
 
void CreateUDN(Graph &G);//实现细节隐藏
void DFS(Graph G, int v);
void DFSTraverse(Graph G){ 
    int v;
    for(v = 0; v < G.vexnum; ++v)  visited[v] = 0;    
    for(v = 0; v < G.vexnum; ++v)
        if(!visited[v])  DFS(G, v); 
}
int main(){
    Graph G;
    CreateUDN(G);
    DFSTraverse(G);
    return 0;
}

/* 请在这里填写答案 */

输入样例：

输入第1行为结点数vexnum和边数arcnum。第2行为结点的值，依次输入arcnum行，每行输入两个结点的值表示该两个结点互为邻接点。

8 8
ABCDEFGH
A B
A C
B D
B E
C F
C G
D H
E H

输出样例：

遍历序列。

A B D H E C F G 

解析

void DFS(Graph G, int v) {
    // 访问当前顶点v，输出顶点值（带空格，匹配样例格式）
    printf("%c ", G.vexs[v]);
    // 标记顶点v为已访问
    visited[v] = 1;
    
    // 遍历所有顶点u，查找v的邻接顶点
    for (int u = 0; u < G.vexnum; ++u) {
        // 若u未访问且v与u之间存在边（邻接矩阵值为1）
        if (!visited[u] && G.arcs[v][u] == 1) {
            // 递归访问u
            DFS(G, u);
        }
    }
}

1-7 最小生成树（普里姆算法）

分数 4

作者 王东

单位 贵州师范学院

试实现普里姆最小生成树算法。

函数接口定义：

void Prim(AMGraph G, char u);

其中 G 是基于邻接矩阵存储表示的无向图，u表示起点

裁判测试程序样例：

#include <iostream>
#define MVNum 10
#define MaxInt 32767 
using namespace std;

struct edge{
    char adjvex;
    int lowcost;
}closedge[MVNum];

typedef struct{ 
    char vexs[MVNum];   
    int arcs[MVNum][MVNum]; 
    int vexnum,arcnum;
}AMGraph;
int LocateVex(AMGraph G , char v);//实现细节隐藏
int Min(AMGraph G);//实现细节隐藏
int CreateUDN(AMGraph &G);//实现细节隐藏

void Prim(AMGraph G, char u);

int main(){
    AMGraph G;
    CreateUDN(G);
    char u;
    cin >> u;
    Prim(G , u);
    return 0;
}

/* 请在这里填写答案 */

输入样例：

第1行输入结点数vexnum和边数arcnum。第2行输入vexnum个字符表示结点的值，接下来依次输入arcnum行，每行输入3个值，前两个字符表示结点，后一个数表示两个结点之间边的权值。最后一行输入一个字符表示最小生成树的起始结点。

7 9
0123456
0 1 28
0 5 10
1 2 16
1 6 14
2 3 12
3 6 18
3 4 22
4 5 25
4 6 24
0

输出样例：

按最小生成树的生成顺序输出每条边。

0->5
5->4
4->3
3->2
2->1
1->6

解析

void Prim(AMGraph G, char u) {
    // 1. 找到起点u在顶点数组中的索引v0
    int v0 = LocateVex(G, u);

    // 2. 初始化closedge数组：记录每个顶点到生成树的最短边（邻接点+权值）
    for (int i = 0; i < G.vexnum; ++i) {
        if (i != v0) {
            closedge[i].adjvex = u;  // 初始时，所有顶点的最短边邻接点都是起点u
            closedge[i].lowcost = G.arcs[v0][i];  // 边权为起点到该顶点的权值（无边为MaxInt）
        } else {
            closedge[i].lowcost = 0;  // 起点已加入生成树，lowcost=0标记
        }
    }

    // 3. 生成最小生成树：共需添加vexnum-1条边（n个顶点的生成树有n-1条边）
    for (int i = 1; i < G.vexnum; ++i) {
        // 3.1 找到当前未加入生成树、且到生成树权值最小的顶点k（Min函数已实现）
        int k = Min(G);

        // 3.2 输出当前添加的边：closedge[k].adjvex（生成树内顶点）→ G.vexs[k]（新加入顶点）
        cout << closedge[k].adjvex << "->" << G.vexs[k] << endl;

        // 3.3 标记顶点k已加入生成树
        closedge[k].lowcost = 0;

        // 3.4 更新closedge数组：以k为新的生成树顶点，更新其他顶点到生成树的最短边
        for (int j = 0; j < G.vexnum; ++j) {
            // 条件：j未加入生成树（lowcost≠0），且k到j的边权 < j当前到生成树的最短边权
            if (closedge[j].lowcost != 0 && G.arcs[k][j] < closedge[j].lowcost) {
                closedge[j].lowcost = G.arcs[k][j];  // 更新最短边权
                closedge[j].adjvex = G.vexs[k];      // 更新最短边的邻接点（生成树内的k）
            }
        }
    }
}

1-8 拓扑排序

分数 4

作者 YJ

单位 西南石油大学

一项工程由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其他子任务后才能执行。例如，下图表示了一项工程若干子任务之间的先后关系。

编写函数输出所有子任务的拓扑序列。

函数接口定义：

Status Push_SeqStack(SeqStack &s, ElemType x)//入栈，x入到s栈中
void topsort( ALGraph &G)
{
   int i,v,w;
   int cnt=0;//计数器初始化为0
   EdgeNode  *ptr;
   SeqStack st;
   InitStack_Sq(st);
   for(i=0;i<G.n;i++)
   {
     if(___________________)
        Push_SeqStack(st,i);
   }
  while(!Empty_Sq(st))
  {
     Pop_SeqStack( st, v);//出栈一次，出栈元素放在v中
     printf("%s ",G.adjlist[v].vertex);
     ____________;
     ptr=G.adjlist[v].firstedge; //ptr指向第一个边结点
     while(ptr!=NULL)//只要有边
     {
       w=ptr->adjvex;
    __________________________;
       if(G.adjlist[w].Indegree==0)
          ____________________;
       ptr=ptr->next;
     }
  }
  if(cnt<G.n)
    printf("后续无法输出！\n");
}

其中s 为顺序栈，x为入栈的元素，G 为有向图，采用邻接表存储。

裁判测试程序样例：

#include <stdio.h>
//#include "conio.h"
#include <stdlib.h>
#include <string.h>
#define  TRUE   1
#define  FALSE  0
#define  OK     1
#define  ERROR 0
#define  OVERFLOW  -1
#define MAXSIZE 30
#define VERTEX_MAX 30   /*最大顶点数*/
#define VEX_NUM 10
typedef int Status;
typedef char Vextype[20];  /*顶点类型*/
typedef int ElemType;
typedef struct
{ ElemType elem[MAXSIZE];
  int top;
  }SeqStack;                                      /*定义顺序栈结构*/
typedef struct node       /*边结点定义*/
 {
    int  adjvex;          /*邻接点域*/
    struct node  *next; /*指向下一个边结点的指针域*/
  }EdgeNode;
typedef struct vnode   /*表头结点定义*/
 { int Indegree;        /*顶点入度域*/
   Vextype  vertex;     /*顶点信息*/
   EdgeNode   *firstedge;
  }VertexNode;
typedef struct                        /*图的邻接表存储*/
 { VertexNode adjlist[VERTEX_MAX];
   int n,e;                            /*顶点数和边数*/
 } ALGraph;


void InitStack_Sq(SeqStack &s)                     /*初始化栈操作*/
  {
    s.top=-1;  //s.top从-1开始，指向实际的栈顶元素
  }/*InitStack_sq*/

int Empty_Sq(SeqStack s)                       /*判栈是否为空*/
  {if(s.top==-1)
     return 1;
   else
      return 0;
  }/*Empty_sq*/
Status Push_SeqStack(SeqStack &s, ElemType x)//入栈
 {//补充完整

 }

Status  Pop_SeqStack(SeqStack &s, ElemType &y)//出栈
   {  if  (Empty_Sq(s))  return OVERFLOW;           /* 栈空不能出栈 */
       else  {  y=s.elem[s.top];
                s.top--;  return OK;
              }                                         /* 栈顶元素存入*y，返回 */
   }
   void CreateALGraph(ALGraph &G) /*创建有向图的邻接表*/
{ int i,v,w;
  int Indegree[VERTEX_MAX]={0};
  EdgeNode *s;
  scanf("%d,%d",&(G.n),&(G.e)); /*输入顶点数n和弧数m*/
  for (i=0;i<G.n;i++)
     { scanf("%s",G.adjlist[i].vertex);
       G.adjlist[i].firstedge=NULL;//给每个顶点的firstedge域赋初值
     }
  for (w=0;w<G.e;w++) /*建立边表*/
     { scanf("%d,%d",&i,&v);
       s=(EdgeNode*)malloc(sizeof(EdgeNode));
       s->adjvex=v;
       Indegree[v]++;  /*统计各顶点的入度*/
       s->next=G.adjlist[i].firstedge;    /*前插方法*/
       G.adjlist[i].firstedge=s;
     }
   for(i=0;i<G.n;i++)
     G.adjlist[i].Indegree=Indegree[i];
  }/*CreateALGraph*/
void topsort( ALGraph &G)
{
}

int main()
{
    ALGraph g;
    CreateALGraph(g);
    printf("拓扑序列为：");
    topsort(g);
    return 0;
}
/* 请在这里填写答案 */

输入样例：

在这里给出一组输入。例如：

6,5
C1
C2
C3
C4
C5
C6
0,2
1,2
1,5
2,3
3,4

输出样例：

在这里给出相应的输出。例如：

拓扑序列为：C2 C6 C1 C3 C4 C5 

解析

// 1. 补全入栈函数 Push_SeqStack
Status Push_SeqStack(SeqStack &s, ElemType x) {
    if (s.top == MAXSIZE - 1) { // 栈满判断
        return OVERFLOW;
    }
    s.elem[++s.top] = x; // 栈顶指针先加1，再存入元素
    return OK;
}

// 2. 补全拓扑排序函数 topsort
void topsort(ALGraph &G) {
    int i, v, w;
    int cnt = 0; // 计数器初始化为0（统计输出的顶点数）
    EdgeNode *ptr;
    SeqStack st;
    InitStack_Sq(st);
    for (i = 0; i < G.n; i++) {
        // 空1：将入度为0的顶点入栈
        if (G.adjlist[i].Indegree == 0)
            Push_SeqStack(st, i);
    }
    while (!Empty_Sq(st)) {
        Pop_SeqStack(st, v); // 出栈一次，出栈元素放在v中
        printf("%s ", G.adjlist[v].vertex);
        // 空2：输出一个顶点后，计数器加1
        cnt++;
        ptr = G.adjlist[v].firstedge; // ptr指向第一个边结点
        while (ptr != NULL) { // 只要有边
            w = ptr->adjvex;
            // 空3：v的邻接顶点w的入度减1（v已完成，解除对w的依赖）
            G.adjlist[w].Indegree--;
            if (G.adjlist[w].Indegree == 0)
                // 空4：w的入度为0，入栈等待输出
                Push_SeqStack(st, w);
            ptr = ptr->next;
        }
    }
    if (cnt < G.n)
        printf("后续无法输出！\n"); // 存在环，拓扑排序失败
}

2-1 列出连通集

分数 7

作者 陈越

单位 浙江大学

给定一个有 n 个顶点和 m 条边的无向图，请用深度优先遍历（DFS）和广度优先遍历（BFS）分别列出其所有的连通集。假设顶点从 0 到 n−1 编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:

输入第 1 行给出 2 个整数 n (0<n≤10) 和 m，分别是图的顶点数和边数。随后 m 行，每行给出一条边的两个端点。每行中的数字之间用 1 空格分隔。

输出格式:

按照"{ v1 v2 … v**k }"的格式，每行输出一个连通集。先输出 DFS 的结果，再输出 BFS 的结果。

输入样例:

8 6
0 7
0 1
2 0
4 1
2 4
3 5

输出样例:

{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

解析

#include <iostream>
#include <vector>
#include <algorithm>  // 用于 fill 函数重置访问标记
using namespace std;

// 全局变量（简化函数参数传递，适配n≤10的约束）
int n, m;                  // 顶点数、边数
int arcs[10][10] = {0};    // 邻接矩阵（无向图，初始全0，有边置1）
int visited[10] = {0};     // 访问标记（0=未访问，1=已访问）

// DFS 深度优先遍历，收集单个连通集
void DFS(int v, vector<int>& conn_set) {
    visited[v] = 1;                // 标记当前顶点为已访问
    conn_set.push_back(v);         // 加入连通集
    
    // 按编号递增顺序访问邻接点（关键规则）
    for (int i = 0; i < n; ++i) {
        // 邻接矩阵值为1（有边）且顶点未访问
        if (arcs[v][i] == 1 && !visited[i]) {
            DFS(i, conn_set);      // 递归深入遍历
        }
    }
}

// BFS 广度优先遍历，收集单个连通集
void BFS(int v, vector<int>& conn_set) {
    int queue[10];  // 数组模拟队列（n≤10，足够容纳所有顶点）
    int front = 0, rear = 0;       // 队列头（出队）、尾（入队）指针
    
    visited[v] = 1;
    queue[rear++] = v;             // 起点入队
    conn_set.push_back(v);         // 加入连通集
    
    while (front < rear) {
        int u = queue[front++];    // 出队当前顶点
        
        // 按编号递增顺序访问邻接点（关键规则）
        for (int i = 0; i < n; ++i) {
            if (arcs[u][i] == 1 && !visited[i]) {
                visited[i] = 1;
                conn_set.push_back(i);
                queue[rear++] = i; // 邻接点入队
            }
        }
    }
}

// 输出单个连通集（按 "{ v1 v2 ... vk }" 格式）
void print_conn_set(const vector<int>& conn_set) {
    cout << "{ ";
    for (int i = 0; i < conn_set.size(); ++i) {
        if (i > 0) cout << " ";    // 元素间加空格
        cout << conn_set[i];
    }
    cout << " }" << endl;
}

int main() {
    // 1. 读取输入，构建邻接矩阵
    cin >> n >> m;
    for (int k = 0; k < m; ++k) {
        int u, v;
        cin >> u >> v;
        arcs[u][v] = 1;  // 无向图：双向置1
        arcs[v][u] = 1;
    }

    // 2. DFS 遍历所有连通集（先输出DFS结果）
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {  // 找到未访问的顶点，作为连通集起点
            vector<int> conn_set;
            DFS(i, conn_set);
            print_conn_set(conn_set);
        }
    }

    // 3. 重置访问标记，准备BFS遍历
    fill(visited, visited + 10, 0);

    // 4. BFS 遍历所有连通集（后输出BFS结果）
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {  // 找到未访问的顶点，作为连通集起点
            vector<int> conn_set;
            BFS(i, conn_set);
            print_conn_set(conn_set);
        }
    }

    return 0;
}

2-2 旅游规划

分数 7

作者 陈越

单位 浙江大学

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:

输入说明：输入数据的第 1 行给出 4 个正整数 n、m、s、d，其中 n（2≤n≤500）是城市的个数，顺便假设城市的编号为 0~(n−1)；m 是高速公路的条数；s 是出发地的城市编号；d 是目的地的城市编号。随后的 m 行中，每行给出一条高速公路的信息，分别是：城市 1、城市 2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过 500。输入保证解的存在。

输出格式:

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出样例:

3 40

解析

#include <stdio.h>
#include <string.h>
#define INF 1000000000  // 定义无穷大（大于最大可能距离/费用）
#define MAXN 501        // 城市最大数量

int main() {
    int n, m, s, d;
    scanf("%d %d %d %d", &n, &m, &s, &d);
    
    // 邻接矩阵：dist[a][b]表示a到b的距离，cost[a][b]表示a到b的费用
    int dist[MAXN][MAXN], cost[MAXN][MAXN];
    // 初始化邻接矩阵为无穷大
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = INF;
            cost[i][j] = INF;
        }
        dist[i][i] = 0;  // 自身到自身的距离为0
        cost[i][i] = 0;  // 自身到自身的费用为0
    }
    
    // 读取m条高速公路信息（无向图，双向赋值）
    for (int i = 0; i < m; i++) {
        int a, b, len, fee;
        scanf("%d %d %d %d", &a, &b, &len, &fee);
        dist[a][b] = len;
        dist[b][a] = len;
        cost[a][b] = fee;
        cost[b][a] = fee;
    }
    
    // min_dist：起点s到各城市的最短距离；min_cost：对应最短距离的最小费用
    int min_dist[MAXN], min_cost[MAXN];
    bool visited[MAXN];  // 标记城市是否已确定最短路径
    memset(visited, false, sizeof(visited));
    
    // 初始化min_dist和min_cost为起点s到各城市的直接值
    for (int i = 0; i < n; i++) {
        min_dist[i] = dist[s][i];
        min_cost[i] = cost[s][i];
    }
    visited[s] = true;  // 起点自身已确定
    
    // Dijkstra算法主循环（共需确定n-1个城市的最短路径）
    for (int i = 0; i < n - 1; i++) {
        // 步骤1：找到当前未访问且min_dist最小的城市u
        int u = -1;
        int min_len = INF;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && min_dist[j] < min_len) {
                min_len = min_dist[j];
                u = j;
            }
        }
        if (u == -1) break;  // 题目保证有解，此句可忽略
        visited[u] = true;   // 标记u为已确定
        
        // 步骤2：松弛操作，更新u的邻接城市v的距离和费用
        for (int v = 0; v < n; v++) {
            // 仅处理未访问且u和v之间有边的城市
            if (!visited[v] && dist[u][v] != INF) {
                // 情况1：经u到v的路径更短，更新距离和费用
                if (min_dist[v] > min_dist[u] + dist[u][v]) {
                    min_dist[v] = min_dist[u] + dist[u][v];
                    min_cost[v] = min_cost[u] + cost[u][v];
                }
                // 情况2：路径长度相同，但费用更低，仅更新费用
                else if (min_dist[v] == min_dist[u] + dist[u][v]) {
                    if (min_cost[v] > min_cost[u] + cost[u][v]) {
                        min_cost[v] = min_cost[u] + cost[u][v];
                    }
                }
            }
        }
    }
    
    // 输出目的地d的最短距离和最小费用
    printf("%d %d\n", min_dist[d], min_cost[d]);
    return 0;
}

2-3 公路村村通

分数 7

作者 陈越

单位 浙江大学

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:

输入数据包括城镇数目正整数 n（≤1000）和候选道路数目 m（≤3n）；随后的 m 行对应 m 条道路，每行给出 3 个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从 1 到 n 编号。

输出格式:

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出 −1，表示需要建设更多公路。

输入样例:

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例:

12

解析

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定义边的结构体：存储两个顶点和边权
struct Edge {
    int u;     // 起点（城镇编号1~n）
    int v;     // 终点
    int weight; // 道路成本
    // 重载小于号，用于边按权值升序排序
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

const int MAXN = 1001; // 城镇最大编号（1~1000）
int parent[MAXN];      // 并查集：parent[i]表示i的父节点
int rank_[MAXN];       // 并查集：rank_[i]表示i所在树的秩（用于按秩合并）

// 并查集初始化：每个城镇初始为自己的父节点
void initUnionFind(int n) {
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
        rank_[i] = 1; // 初始秩为1（树高为1）
    }
}

// 并查集查找：找顶点x的根节点（带路径压缩，提高效率）
int findRoot(int x) {
    if (parent[x] != x) {
        // 路径压缩：将x的父节点直接指向根节点，减少后续查找次数
        parent[x] = findRoot(parent[x]);
    }
    return parent[x];
}

// 并查集合并：合并x和y所在的集合（按秩合并，避免树过高）
bool unionSets(int x, int y) {
    int rootX = findRoot(x);
    int rootY = findRoot(y);
    
    if (rootX == rootY) {
        return false; // x和y已在同一集合，合并失败（边无效）
    }
    
    // 按秩合并：秩小的树合并到秩大的树的根节点下
    if (rank_[rootX] < rank_[rootY]) {
        parent[rootX] = rootY;
    } else {
        parent[rootY] = rootX;
        // 若秩相等，合并后根节点的秩+1
        if (rank_[rootX] == rank_[rootY]) {
            rank_[rootX]++;
        }
    }
    return true; // 合并成功（边有效）
}

int main() {
    int n, m; // n=城镇数，m=候选道路数
    cin >> n >> m;
    
    vector<Edge> edges(m); // 存储所有道路
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
    }
    
    // 边界情况：只有1个城镇，无需道路，成本为0
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }
    
    // 步骤1：将所有道路按成本升序排序（克鲁斯卡尔核心）
    sort(edges.begin(), edges.end());
    
    // 步骤2：初始化并查集，维护连通分量
    initUnionFind(n);
    
    int totalCost = 0;   // 最小生成树总成本
    int validEdges = 0;  // 已选中的有效边数（生成树需n-1条边）
    
    // 步骤3：遍历排序后的边，筛选有效边构建生成树
    for (const auto& edge : edges) {
        if (unionSets(edge.u, edge.v)) { // 边的两个顶点不在同一集合
            totalCost += edge.weight;    // 累加成本
            validEdges++;                // 有效边数+1
            
            // 生成树已完成（n个顶点需n-1条边），提前退出
            if (validEdges == n - 1) {
                break;
            }
        }
    }
    
    // 步骤4：判断是否所有城镇连通
    if (validEdges == n - 1) {
        cout << totalCost << endl; // 连通，输出总成本
    } else {
        cout << -1 << endl;        // 不连通，输出-1
    }
    
    return 0;
}

2-4 最短工期

分数 7

作者 陈越

单位 浙江大学

一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。

输入格式：

首先第一行给出两个正整数：项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。

输出格式：

如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。

输入样例 1：

9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4

输出样例 1：

18

输入样例 2：

4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

输出样例 2：

Impossible

解析

#include <stdio.h>
#include <stdlib.h>
#define MAXN 101  // 里程碑最大数量（≤100）

// 邻接表边节点结构
typedef struct Edge {
    int v;        // 邻接节点（任务结束里程碑）
    int w;        // 任务时长
    struct Edge *next;  // 下一条边
} Edge;

Edge *adj[MAXN];       // 邻接表
int in_degree[MAXN];   // 每个节点的入度
int earliest[MAXN];    // 每个节点的最早开始时间
int N, M;              // N：里程碑数，M：任务数

// 初始化邻接表、入度数组、最早时间数组
void init() {
    for (int i = 0; i < MAXN; i++) {
        adj[i] = NULL;
        in_degree[i] = 0;
        earliest[i] = 0;
    }
}

// 向邻接表添加边（u→v，时长w）
void addEdge(int u, int v, int w) {
    Edge *e = (Edge *)malloc(sizeof(Edge));
    e->v = v;
    e->w = w;
    e->next = adj[u];  // 前插法插入边
    adj[u] = e;
}

int main() {
    init();
    scanf("%d %d", &N, &M);
    
    // 读取M个任务，构建邻接表并统计入度
    for (int i = 0; i < M; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        addEdge(u, v, w);
        in_degree[v]++;  // 终点v的入度+1
    }
    
    // 数组模拟队列，存储入度为0的节点
    int q[MAXN], front = 0, rear = 0;
    for (int i = 0; i < N; i++) {
        if (in_degree[i] == 0) {
            q[rear++] = i;  // 入度为0的节点入队
        }
    }
    
    int count = 0;  // 记录拓扑排序处理的节点数
    while (front < rear) {
        int u = q[front++];  // 出队节点u
        count++;
        
        // 遍历u的所有邻接边（处理依赖u的任务）
        Edge *p = adj[u];
        while (p != NULL) {
            int v = p->v;
            int w = p->w;
            
            // 更新v的最早开始时间（取最长路径）
            if (earliest[v] < earliest[u] + w) {
                earliest[v] = earliest[u] + w;
            }
            
            // v的入度减1（前置任务u已完成）
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q[rear++] = v;  // v无前置依赖，入队
            }
            
            p = p->next;  // 遍历下一条边
        }
    }
    
    // 判断是否有环（处理的节点数小于总节点数）
    if (count != N) {
        printf("Impossible\n");
        return 0;
    }
    
    // 查找最早完工时间（所有节点最早开始时间的最大值）
    int max_earliest = 0;
    for (int i = 0; i < N; i++) {
        if (earliest[i] > max_earliest) {
            max_earliest = earliest[i];
        }
    }
    printf("%d\n", max_earliest);
    
    // 释放邻接表内存（可选，不影响结果）
    for (int i = 0; i < N; i++) {
        Edge *p = adj[i];
        while (p != NULL) {
            Edge *temp = p;
            p = p->next;
            free(temp);
        }
    }
    
    return 0;
}

2-5 图的连通性判断

分数 7

作者 陈越

单位 浙江大学

请编写程序，用广度优先搜索输出给定无向图中的各个连通分量，并判断给定的无向图是否连通。
注意输出顺序规定如下：

• 每个连通分量的输出从其中编号最小的顶点开始；
• 不同连通分量按其第一个顶点的编号增序输出，每个连通分量占一行；
• 当一个顶点有多个邻接点时，按其输入的逆序进行访问，即最后输入的邻接点，在广度优先搜索中应被最先访问输出。

输入格式：

输入首先在第一行给出图中最大顶点数量，即正整数 kMaxVertex（≤10）。
第二行给出两个正整数，依次为当前要创建的图的顶点数 n 和边数 m（保证顶点数至少为 2 且不超过最大顶点数量）。
第三行给出 n 个英文字母，顺序对应每个顶点的信息。
随后 m 行，每行给出一条无向边的两个端点的编号、以及边的权重。顶点编号从 0 开始，权重（≤230）为整数。
同行数字、字符均以一个空格分隔。

输出格式：

按照题面中规定的顺序，输出图中的连通分量每个顶点的信息。每个连通分量占一行，字符间不要有空格。
随后，如果图不连通，则在一行中输出 有 x 个连通分量，其中 x 是连通分量的个数。
最后一行输出 该图连通性为 y，其中图连通时 y 值为 1，否则为 0。

输入样例：

10
6 7
a b c d e f
2 0 2
2 3 1
3 0 3
3 4 4
2 4 2
4 0 5
4 5 1

输出样例：

aedcf
b
有 2 个连通分量
该图连通性为 0

解析

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int kMaxVertex;
    if (!(cin >> kMaxVertex)) return 0;

    int n, m;
    cin >> n >> m;

    vector<char> info(n);
    for (int i = 0; i < n; i++) cin >> info[i];

    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        // 无向图：双向加入，按输入顺序 push_back（后面 BFS 时倒序访问）
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> visited(n, 0);
    vector<vector<int>> components;

    for (int start = 0; start < n; start++) {
        if (!visited[start]) {
            queue<int> q;
            vector<int> comp;
            visited[start] = 1;
            q.push(start);

            while (!q.empty()) {
                int u = q.front(); q.pop();
                comp.push_back(u);

                // 安全地将 size() 转换为 int，倒序遍历邻接点，实现“输入逆序访问”的要求
                for (int i = (int)adj[u].size() - 1; i >= 0; --i) {
                    int v = adj[u][i];
                    if (!visited[v]) {
                        visited[v] = 1;
                        q.push(v);
                    }
                }
            }

            components.push_back(comp);
        }
    }

    // 输出每个连通分量（按顶点字符 info[]），每行不空格
    for (auto &comp : components) {
        for (int v : comp) cout << info[v];
        cout << "\n";
    }

    int cnt = (int)components.size();
    if (cnt > 1) {
        cout << "有 " << cnt << " 个连通分量\n";
        cout << "该图连通性为 0\n";
    } else {
        cout << "该图连通性为 1\n";
    }

    return 0;
}

2-6 求最小生成树的Prim算法

分数 8

作者 陈越

单位 浙江大学

请编写程序，实现在带权的无向图中求最小生成树的 Prim 算法。
注意：当多个待收录顶点到当前点集的距离等长时，按编号升序进行收录。

输入格式：

输入首先在第一行给出两个正整数，依次为当前要创建的图的顶点数 n（≤100）和边数 m。
随后 m 行，每行给出一条无向边两端点的编号、权重。顶点编号从 0 开始，权重（≤100）为整数。同行数字均以一个空格分隔。

输出格式：

参考样例。
首先在一行中输出 total weight = x，其中 x 为最小生成树中所有边的总权重。如果最小生成树不存在，则 x 为 −1。
随后在一行中按顶点编号升序输出每个顶点在最小生成树中的父结点的编号。为输出简单起见，每个数字后有一个空格。
注意：此处默认顶点 0 为最小生成树的根结点，其父结点编号规定为 −1。算法初始化时，所有顶点（除了根结点）的父结点编号默认为 0。

输入样例 1：

6 9
0 1 1
0 2 3
1 2 6
1 3 2
2 3 7
2 4 5
2 5 4
3 5 8
4 5 1

输出样例 1：

total weight = 11
-1 0 0 1 5 2 

输入样例 2：

7 9
0 1 1
0 2 3
1 2 6
1 3 2
2 3 7
2 4 5
2 5 4
3 5 8
4 5 1

输出样例 2：

total weight = -1
-1 0 0 1 5 2 0 

解析

#include <stdio.h>
#include <stdbool.h>
#define INF 1000  // 权重最大值≤100，用1000表示无边
#define MAXN 101  // 顶点数≤100，编号0~100

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 1. 初始化邻接矩阵
    int adj[MAXN][MAXN];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            adj[i][j] = INF;
        }
        adj[i][i] = 0;  // 自身到自身距离为0
    }
    
    // 2. 读取边信息（无向图，双向赋值）
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u][v] = w;
        adj[v][u] = w;
    }
    
    // 3. 初始化辅助数组
    int dist[MAXN], parent[MAXN];
    bool visited[MAXN];
    int total_weight = 0;  // 最小生成树总权重
    int count = 0;         // 已收录的顶点数（除根0外）
    
    for (int i = 0; i < n; i++) {
        dist[i] = adj[0][i];    // 初始距离为根0到各顶点的直接距离
        parent[i] = 0;          // 初始父节点默认为0（除根外）
        visited[i] = false;     // 初始均未收录
    }
    parent[0] = -1;  // 根节点父节点为-1
    visited[0] = true;  // 根节点已收录
    
    // 4. Prim算法主循环：需收录n-1个顶点
    for (int i = 0; i < n - 1; i++) {
        // 步骤1：找未收录顶点中dist最小且编号最小的顶点u
        int min_dist = INF;
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }
        
        // 若找不到u，说明图不连通，生成树不存在
        if (u == -1) {
            total_weight = -1;
            break;
        }
        
        // 步骤2：收录u到生成树
        visited[u] = true;
        total_weight += min_dist;
        count++;
        
        // 步骤3：通过u优化邻接顶点的dist和parent
        for (int v = 0; v < n; v++) {
            if (!visited[v] && adj[u][v] < dist[v]) {
                dist[v] = adj[u][v];
                parent[v] = u;
            }
        }
    }
    
    // 最终判断：若收录顶点数不足n-1，确认生成树不存在
    if (count != n - 1) {
        total_weight = -1;
    }
    
    // 5. 输出结果
    printf("total weight = %d\n", total_weight);
    for (int i = 0; i < n; i++) {
        printf("%d ", parent[i]);
    }
    printf("\n");
    
    return 0;
}

2-7 拓扑排序

分数 8

作者 陈越

单位 浙江大学

请编写程序，实现对有向无权图中的顶点进行拓扑排序的算法。
注意：如果拓扑序不唯一，输出任何一个序列都可以，由特殊裁判程序判定正确性。

输入格式：

输入首先在第一行给出两个正整数，依次为当前要创建的图的顶点数 n（≤100）和边数 m。
随后一行顺序给出 n 个顶点对应的字符串，由不超过 3 个英文字母或数字组成。
接下来 m 行，每行给出一条有向边的起点编号、终点编号。顶点编号从 0 开始。同行数字和字符串均以一个空格分隔。

输出格式：

参考样例。
首先在一行中输出 该图拓扑序存在性为 x，其中 x 为 1 表示该图顶点有拓扑序，为 0 表示没有。
随后在一行中按顶点拓扑序存输出每个顶点对应的字符串。为输出简单起见，每个字符串后有一个空格。
注意：如果拓扑序不存在，最后一行可以输出任何字符，均判为正确。

输入样例 1：

8 8
C0 C1 C2 C3 C4 C5 C6 C7
0 2
0 4
1 2
1 4
3 4
4 5
4 6
5 7

输出样例 1：

该图拓扑序存在性为 1
C0 C1 C3 C2 C4 C6 C5 C7 

输入样例 2：

8 9
C0 C1 C2 C3 C4 C5 C6 C7
0 2
0 4
1 2
1 4
3 4
4 5
4 6
5 7
7 4

输出样例 2：

该图拓扑序存在性为 0
这里输出什么都不重要

解析

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 101  // 顶点数≤100，预留1个冗余位置

// 边节点结构（邻接表用）
typedef struct EdgeNode {
    int adjvex;                // 邻接顶点的编号
    struct EdgeNode *next;     // 指向下一个边节点
} EdgeNode;

// 顶点结构（邻接表表头）
typedef struct VNode {
    char data[4];              // 顶点字符串（最多3个字符+结束符'\0'）
    EdgeNode *firstedge;       // 指向第一个边节点
} VNode;

// 图结构（邻接表存储）
typedef struct {
    VNode adjlist[MAXN];       // 邻接表数组（索引=顶点编号）
    int in_degree[MAXN];       // 每个顶点的入度
    int n, m;                  // 顶点数n，边数m
} ALGraph;

int main() {
    ALGraph G;
    int i;

    // 1. 读取输入：顶点数n、边数m
    scanf("%d %d", &G.n, &G.m);

    // 2. 读取n个顶点的字符串，初始化邻接表表头
    for (i = 0; i < G.n; i++) {
        scanf("%s", G.adjlist[i].data);  // 读取顶点字符串
        G.adjlist[i].firstedge = NULL;   // 边链表初始为空
        G.in_degree[i] = 0;              // 入度初始化为0
    }

    // 3. 读取m条有向边，构建邻接表+更新入度数组
    for (i = 0; i < G.m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);  // u：起点编号，v：终点编号

        // 创建边节点（前插法插入邻接表，效率更高）
        EdgeNode *p = (EdgeNode *)malloc(sizeof(EdgeNode));
        p->adjvex = v;
        p->next = G.adjlist[u].firstedge;
        G.adjlist[u].firstedge = p;

        G.in_degree[v]++;  // 终点v的入度+1（增加一个前置依赖）
    }

    // 4. 初始化队列（数组模拟，n≤100足够用）
    int q[MAXN], front = 0, rear = 0;
    int topo_seq[MAXN], count = 0;  // 存储拓扑序列的顶点编号，count为序列长度

    // 将所有入度为0的顶点入队（无依赖，可优先输出）
    for (i = 0; i < G.n; i++) {
        if (G.in_degree[i] == 0) {
            q[rear++] = i;
        }
    }

    // 5. 执行Kahn算法核心逻辑
    while (front < rear) {
        int u = q[front++];  // 出队一个顶点u
        topo_seq[count++] = u;  // 将u加入拓扑序列

        // 遍历u的所有邻接顶点v，解除u对v的依赖
        EdgeNode *p = G.adjlist[u].firstedge;
        while (p != NULL) {
            int v = p->adjvex;
            G.in_degree[v]--;  // v的入度减1（依赖减少一个）

            // 若v的入度变为0（所有依赖已解除），入队等待输出
            if (G.in_degree[v] == 0) {
                q[rear++] = v;
            }

            p = p->next;  // 遍历下一个邻接顶点
        }
    }

    // 6. 判断拓扑序是否存在（序列长度=顶点数则存在）
    int exist = (count == G.n) ? 1 : 0;
    printf("该图拓扑序存在性为 %d\n", exist);

    // 7. 输出拓扑序列（存在则输出，不存在可输出任意内容）
    if (exist) {
        for (i = 0; i < G.n; i++) {
            printf("%s ", G.adjlist[topo_seq[i]].data);  // 每个字符串后带空格
        }
    }
    printf("\n");  // 保证输出格式统一（即使不存在也换行）

    // 8. 释放内存（可选，题目未要求，但避免内存泄漏）
    for (i = 0; i < G.n; i++) {
        EdgeNode *p = G.adjlist[i].firstedge;
        while (p != NULL) {
            EdgeNode *temp = p;
            p = p->next;
            free(temp);
        }
    }

    return 0;
}

2-8 求图中关键活动

分数 8

作者 陈越

单位 浙江大学

请编写程序，实现求带权的有向图中关键活动的算法。

输入格式：

输入首先在第一行给出两个正整数，依次为当前要创建的图的顶点数 n（≤100）和边数 m。
随后 m 行，每行给出一条有向边的起点编号、终点编号、权重。顶点编号从 0 开始，权重（≤100）为整数。同行数字均以一个空格分隔。

输出格式：

按格式 <u, v> 输出关键活动，其中 u 为起点编号，v 为终点编号。按起点编号的升序，每行输出一个活动。起点编号相同时，与输入的顺序相反，即先输入的边后输出。
最后一行输出 关键路径分析结果为 x，其中 x 为 1 表示关键路径已成功求出，为 0 表示不成功。

输入样例 1：

9 12
0 1 5
0 2 3
1 4 4
1 5 2
2 3 6
2 4 1
3 6 7
4 6 3
4 7 5
5 7 6
6 8 2
7 8 8

输出样例 1：

<0, 1>
<1, 4>
<4, 7>
<7, 8>
关键路径分析结果为 1

输入样例 2：

8 9
0 2 3
0 4 5
1 2 12
1 4 7
3 4 9
4 5 2
4 6 1
5 7 2
7 4 41

输出样例 2：

关键路径分析结果为 0

解析

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int v, w, id; // 终点，权重，输入顺序 id
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<Edge>> G(n);         // 正向图
    vector<vector<Edge>> rG(n);        // 反向图
    vector<int> indeg(n, 0);           // 入度
    vector<tuple<int,int,int,int>> edges; // (u,v,w,id)

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w, i});
        rG[v].push_back({u, w, i});
        indeg[v]++;
        edges.push_back({u, v, w, i});
    }

    // ---------- 拓扑排序 ----------
    queue<int> q;
    vector<int> topo;
    for (int i = 0; i < n; i++)
        if (indeg[i] == 0) q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (auto &e : G[u]) {
            indeg[e.v]--;
            if (indeg[e.v] == 0)
                q.push(e.v);
        }
    }

    // 若拓扑点数不足，说明有环
    if ((int)topo.size() < n) {
        cout << "关键路径分析结果为 0";
        return 0;
    }

    // ---------- 求 ve（最长路径） ----------
    vector<int> ve(n, 0);

    for (int u : topo) {
        for (auto &e : G[u]) {
            ve[e.v] = max(ve[e.v], ve[u] + e.w);
        }
    }

    // ---------- 求 vl（最迟开始） ----------
    vector<int> vl(n, ve[topo.back()]); // 初始化为最大 ve

    for (int i = topo.size() - 1; i >= 0; i--) {
        int v = topo[i];
        for (auto &e : G[v]) {
            vl[v] = min(vl[v], vl[e.v] - e.w);
        }
    }

    // 若有不可更新，表示无关键路径
    if (vl[0] < 0) {
        cout << "关键路径分析结果为 0";
        return 0;
    }

    // ---------- 判断关键活动 ----------
    vector<pair<int, pair<int, int>>> critical; 
    // 保存 (u, (v, 输入id))

    for (auto &[u, v, w, id] : edges) {
        int e = ve[u];
        int l = vl[v] - w;
        if (e == l) {
            critical.push_back({u, {v, id}});
        }
    }

    // ---------- 排序输出 ----------
    sort(critical.begin(), critical.end(), [](auto &a, auto &b) {
        if (a.first != b.first)
            return a.first < b.first;             // 起点升序
        return a.second.second > b.second.second; // 输入顺序的反序
    });

    for (auto &p : critical) {
        cout << "<" << p.first << ", " << p.second.first << ">\n";
    }

    cout << "关键路径分析结果为 1";

    return 0;
}

2-9 团结就是力量

分数 9

作者 陈越

单位 浙江大学

常言道：团结就是力量。这里我们定义一个群体是“团结”的，如果这个群体中的任意两个人都是好朋友。并且，我们假定友谊是双向且可传递的，即：若 A 和 B 是朋友、B 和 C 是朋友，则 A 和 C 一定是朋友。下面给定一些人与人之间的关系，你的任务是用最少的努力将他们全部团结起来。

输入格式：

首先在第一行给出两个正整数 n 和 m（均不超过 105），分别为总人数和人与人之间的关系条数。接下来 m 行，每行描述了两个人之间的关系，格式为：

P1 P2 力量值

其中 P1 和 P2 是两个人的编号（所有人从 1 到 n 编号），力量值 是区间 [−103,103] 内的一个非零整数，其为正数时，表示 P1 和 P2 是朋友，这个值是他们团结起来的力量；其为负数时，表示 P1 和 P2 还没有成为朋友，这个值的绝对值是团结他们所需要付出的力量。
此外，如果我们想要将 A 和 B 团结起来，但他们之间的关系并没有给出，则假设团结他们需要付出的力量是个常数 104。

输出格式：

根据输入的人际关系，所有人可以被划分为几个朋友群。一个朋友群的“凝聚力”被定义为这个群中所有朋友间最小的力量值。首先必须在一行中按以下格式输出这些朋友群的信息：

G1-S1 G2-S2 …

其中 Gi 是朋友群的编号，即该群成员的最小编号；Si 是该群的凝聚力。按凝聚力的非递增序输出。当凝聚力并列时，按群规模（即群成员人数）的非递增序输出。如果还是并列，则按群编号的增序输出。一对数据之间用1个空格分隔，行首尾不得有多余空格。
随后在下一行输出将所有人全部团结起来需要的最小力量值。

输入样例：

10 13
8 3 -5
8 6 3
2 5 2
1 8 -1
3 5 -7
7 9 4
9 4 5
7 3 -3
4 3 -4
6 1 2
8 2 -6
7 4 2
6 3 -2

输出样例：

1-2 4-2 2-2 3-0 10-0
10011

解析

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <climits>
using namespace std;

const int MAXN = 1e5 + 10;
const int INF = INT_MAX;
const int DEFAULT = 10000;

// 并查集1：处理正边，构建朋友群
int parent1[MAXN];
int size1[MAXN];
int min_pos1[MAXN];  // 连通分量内最小正边权
int min_node1[MAXN]; // 连通分量内最小节点编号
bool visited[MAXN];  // 标记根节点是否已处理
int gi_of_root[MAXN];// 每个根节点对应的群编号Gi

// 并查集2：处理MST，合并朋友群（查找函数）
int find2(int x, unordered_map<int, int>& parent2_map) {
    if (parent2_map[x] != x) {
        parent2_map[x] = find2(parent2_map[x], parent2_map);
    }
    return parent2_map[x];
}

// 并查集1：查找函数（路径压缩）
int find1(int x) {
    if (parent1[x] != x) {
        parent1[x] = find1(parent1[x]);
    }
    return parent1[x];
}

// 朋友群结构体（用于排序和输出）
struct Group {
    int Gi;    // 群编号（最小节点）
    int Si;    // 凝聚力
    int size;  // 群规模
    bool operator<(const Group& other) const {
        if (Si != other.Si) return Si > other.Si;    // 凝聚力降序
        if (size != other.size) return size > other.size; // 规模降序
        return Gi < other.Gi;    // 群编号升序
    }
};

// 负边结构体（暂存用于后续处理）
struct NegEdge {
    int u, v, w;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // 初始化并查集1
    for (int i = 1; i <= n; ++i) {
        parent1[i] = i;
        size1[i] = 1;
        min_pos1[i] = INF;
        min_node1[i] = i;
        visited[i] = false;
    }

    vector<NegEdge> neg_edges;

    // 处理所有边：分离正边（构建朋友群）和负边（暂存）
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        if (w > 0) {
            // 正边：更新并查集1的连通分量
            int root_u = find1(u);
            int root_v = find1(v);
            if (root_u != root_v) {
                // 按规模合并，保证效率
                if (size1[root_u] < size1[root_v]) swap(root_u, root_v);
                parent1[root_v] = root_u;
                size1[root_u] += size1[root_v];
                // 更新最小正边权和最小节点编号
                min_pos1[root_u] = min({min_pos1[root_u], min_pos1[root_v], w});
                min_node1[root_u] = min(min_node1[root_u], min_node1[root_v]);
            } else {
                // 同一分量，更新最小正边权
                if (w < min_pos1[root_u]) min_pos1[root_u] = w;
            }
        } else {
            // 负边：暂存
            neg_edges.push_back({u, v, w});
        }
    }

    // 收集所有朋友群信息
    vector<Group> groups;
    for (int i = 1; i <= n; ++i) {
        int root = find1(i);
        if (!visited[root]) {
            visited[root] = true;
            Group g;
            g.Gi = min_node1[root];
            g.size = size1[root];
            g.Si = (g.size == 1) ? 0 : min_pos1[root];
            groups.push_back(g);
            gi_of_root[root] = g.Gi; // 记录根节点对应的群编号
        }
    }

    // 按规则排序朋友群
    sort(groups.begin(), groups.end());

    // 输出第一行：朋友群信息
    int k = groups.size();
    for (int i = 0; i < k; ++i) {
        if (i > 0) cout << " ";
        cout << groups[i].Gi << "-" << groups[i].Si;
    }
    cout << "\n";

    // 若只有一个群，无需合并
    if (k == 1) {
        cout << 0 << "\n";
        return 0;
    }

    // 初始化并查集2（用于MST合并群）
    unordered_map<int, int> parent2_map;
    for (auto& g : groups) parent2_map[g.Gi] = g.Gi;

    // 处理负边，构建群间候选边（保留最小权值）
    unordered_map<int, unordered_map<int, int>> edge_map; // edge_map[a][b] = 最小abs(w)
    for (auto& e : neg_edges) {
        int root_u = find1(e.u);
        int root_v = find1(e.v);
        int g1 = gi_of_root[root_u];
        int g2 = gi_of_root[root_v];
        if (g1 == g2) continue; // 同群，跳过
        int a = min(g1, g2), b = max(g1, g2);
        int abs_w = -e.w; // 负边权值取绝对值
        // 更新最小权值
        if (edge_map[a].count(b) == 0 || abs_w < edge_map[a][b]) {
            edge_map[a][b] = abs_w;
        }
    }

    // 提取候选边并排序（按权值升序）
    vector<pair<int, pair<int, int>>> mst_edges;
    for (auto& p1 : edge_map) {
        int a = p1.first;
        for (auto& p2 : p1.second) {
            int b = p2.first, w = p2.second;
            mst_edges.emplace_back(w, make_pair(a, b));
        }
    }
    sort(mst_edges.begin(), mst_edges.end());

    // Kruskal算法求MST
    long long total_effort = 0;
    for (auto& e : mst_edges) {
        int w = e.first;
        int a = e.second.first, b = e.second.second;
        int root_a = find2(a, parent2_map);
        int root_b = find2(b, parent2_map);
        if (root_a != root_b) {
            parent2_map[root_b] = root_a;
            total_effort += w;
        }
    }

    // 计算并查集2的连通分量数（未合并的群数）
    unordered_set<int> root_set;
    for (auto& g : groups) root_set.insert(find2(g.Gi, parent2_map));
    int c = root_set.size();

    // 补充默认边（1e4）的努力
    total_effort += (long long)(c - 1) * DEFAULT;

    // 输出最小努力
    cout << total_effort << "\n";

    return 0;
}