首页 > 其他分享 >11.19

11.19

时间:2024-11-19 23:41:24浏览次数:1  
标签:index 11.19 int 复杂度 vertex 邻接矩阵 顶点

C++ 代码实现:
cpp

include

include

include <unordered_map>

using namespace std;

int main() {
int V, E;
cin >> V >> E;

// 错误处理:顶点个数为0
if (V == 0) {
    cout << "error" << endl;
    return 0;
}

// 错误处理:顶点个数为1,且边个数大于0
if (V == 1 && E > 0) {
    cout << "error" << endl;
    return 0;
}

vector<char> vertices(V);
unordered_map<char, int> vertex_index;

// 读取顶点并建立顶点到索引的映射
for (int i = 0; i < V; ++i) {
    cin >> vertices[i];
    vertex_index[vertices[i]] = i;
}

// 初始化邻接矩阵
vector<vector<int>> adjMatrix(V, vector<int>(V, 0));

// 处理每条边
for (int i = 0; i < E; ++i) {
    char u, v;
    cin >> u >> v;

    // 将边 u -> v 设为 1
    adjMatrix[vertex_index[u]][vertex_index[v]] = 1;
}

// 输出邻接矩阵
for (int i = 0; i < V; ++i) {
    for (int j = 0; j < V; ++j) {
        cout << adjMatrix[i][j] << " ";
    }
    cout << endl;
}

return 0;

}
代码解析:
输入部分:

通过 cin 读取输入的顶点数 V 和边数 E。
如果 V == 0,立即输出 "error"。
如果 V == 1 且 E > 0,输出 "error"。
使用 vector 存储顶点,并通过 unordered_map<char, int> 将每个顶点与其索引关联。
邻接矩阵初始化:

使用二维 vector 初始化邻接矩阵,所有元素默认值为 0,表示没有边。
处理每条边:

对于每条边 (u, v),通过 vertex_index 查找顶点 u 和 v 的索引,然后在邻接矩阵中对应的位置设置为 1。
输出邻接矩阵:

遍历邻接矩阵并打印。
输入输出示例:
输入:
4 4
a b c d
a b
a c
c d
d a
输出:
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
错误输入示例:
输入:
0 0
输出:
error
输入:
1 1
a
a a
输出:
error
复杂度分析:
时间复杂度:O(V^2 + E),初始化邻接矩阵的时间复杂度是 O(V^2),处理每条边的时间复杂度是 O(1),因此总体时间复杂度为 O(V^2 + E)。
空间复杂度:O(V^2),主要是由于存储邻接矩阵的空间。
总结:
该程序能够正确处理邻接矩阵的生成,确保在遇到错误的输入时能进行适当的错误提示,并且能够高效地处理正常的输入数据

标签:index,11.19,int,复杂度,vertex,邻接矩阵,顶点
From: https://www.cnblogs.com/hjz20050621/p/18555864

相关文章

  • 11.19随笔
    这里是11.19随笔。题目留档:使用键盘输入数学表达式(含数字,四种运算符+、-、、/和小括号,其中运算数都是一位数(0~9)),将数学表达式转化成后缀表达式输出,利用后缀表达式求表达式的值并输出。输入格式:输入正确的表达式(可以有空格)后回车,得到后缀表达式和结果。输入括号缺失的表达式,输......
  • 11.19
    refuse用法搭配基本含义和用法‌:refuse的基本意思是“拒绝”,表示由于不情愿或不愿意而对某项要求或事物给予否定的回答或不接受某物或不肯做某事。refuse既可用作及物动词,也可用作不及物动词。用作及物动词时,可接名词、代词或动词不定式作宾语,有时也可接双宾语,其间接宾语可以转化......
  • 每日打卡 11.19 (2)
    includeinclude<string.h>include<windows.h>usingnamespacestd;structstudent{charname[10];intc,math,english;doubleaverage;};intmain(){intindex,n;structstudents[10],temp;cout<<"请输入学生人数:";cin>>......
  • 每日打卡 11.19
    includeinclude<string.h>include<windows.h>usingnamespacestd;structstudent{charname[10];intc,math,english;doubleaverage;};intmain(){intindex,n;structstudents[10],temp;cout<<"请输入学生人数:";cin>>n......
  • 2024.11.19 test
    A给定一个无限长序列的\(0\simn-1\)项,每项满足与\(n\)的差不超过\(1\)。之后的每一项满足\(a_i=\sum_{j=0}^{i-1}[a_j+j\gei]\)。\(q\)次询问第\(p\)个位置的值。\(p\le10^{15}\)。非常难的签到,考虑消去常数,将\(a_i\)全部减去\(n\),那么\(a_i=[a_{i-n-1}=1]-[a_......
  • [考试记录] 2024.11.19 noip模拟赛17
    T1选取字符串warning❗:本题解前缀含量过高。挺典的kmp。考虑到题目中的串都是一个串的前缀,那么所选出来的串,他们的前缀一定是最短的那个串。不妨直接枚举每一个前缀,也就是枚举每一个串,看他们是否可以作为前缀出现,hash即可,复杂度\(\mathcal{O}(N^2)\)。换个思路,考虑有多......
  • 24.11.19
    今日写大作业实验三:JFinal极速开发框架实验 (2024.11.29日前完成)    根据参考资料,学习JFinal极速开发框架的使用并如下任务:    任务一:了解Maven及其使用方法,总结其功能作用(占20%)    任务二:学习JFinal框架,基于Maven建立JFinal工程,并对JFinal框架功能进行总结介绍(占3......
  • 11.19 CW 模拟赛 T1.谁开了小号
    算法嗯,和赛时做法也是没有一点相似之处,寄!挂个\(\rm{TJ}\)题解下载对于暴力,显然可以用\(\rm{dfs}\)实现,这种\(\rm{dfs}\)我还没有见过大概有个想法,每次有两种选择,要么新开集合,要么从前面加一个进去,大概就这样,也比较简单,剪剪枝小数据包过的正解做......
  • 2024.11.19 模拟赛
    11.19模拟赛题目质量点赞!好题!storm普及组模拟题god有趣的dp题key:考察相对位置设计状态\(f(i,j)\)表示考虑后\(i\)个操作,经过了相对坐标为\(j\)的点的概率。转移中,如果这一步不动,相对坐标不变;否则,相对坐标整体平移。答案就是\(f(n,j)\)。fate瞎搞贪心题显然从......
  • 11.19 CW 模拟赛 赛时记录
    看题\(\rm{T1}\)神tmzcy和jmr,what'sup至少看懂题了(雾)\(\rm{T2}\)也是看懂题了,怎么也应该比\(\rm{T1}\)难\(\rm{T3}\)这个类型的题\(100\%\)不会的呀看看能不能骗点算了\(\rm{T4}\)神秘计数,这个类型的题\(100\%\)不会的呀看看能不能骗点算了正序......