首页 > 试题广场 >

生物课程

[编程题]生物课程
𝑅𝑒𝑘𝑖是一名武侦高狙击科的学生，武侦高也设有基础学科，现在她正
在完成生物课的作业。
给出一张𝑛个点𝑚条边的无向图，这张无向图描述了一个细胞，细胞有
三种：X型、Y型还是I型。

如图，虚线方向的链可以无限延伸，现在需要判断给定的图是哪一种
细胞，或者都不是。

输入描述:
第一行，两个正整数𝑛，𝑚。
接下来𝑚行，每行两个正整数𝑢, 𝑣描述一条无向边。


输出描述:
输出这种细胞的类型，若都不是输出NotValid。
示例1

输入

7 6
1 2
1 3
1 4
1 5
5 6
6 7

输出

X
示例2

输入

7 6
1 2
1 3
3 4
1 5
5 6
6 7

输出

Y
示例3

输入

2 1
1 2

输出

I
示例4

输入

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

输出

NotValid

备注:
对于100%的数据，2 ≤ 𝑛 ≤ 500，0 ≤ 𝑚 ≤ 𝑛*(𝑛−1)/2，没有重边和自环。
算法知识视频讲解
开通博客
头像 dadidididi
发表于 2022-04-29 17:55:41
虚线方向的链可以无限延伸 这一点很关键 在X染色体中，只有四个节点有一条连边,四个节点无限延伸后任然只有四个节点只有一条连边 在Y染色体中，只有三个节点有一条连边，三个节点无限延伸后任然只有三个节点只有一条连边 在I染色体中，只有两个节点有一条连边，两个节点无限延伸后任然只有两个节点只有一条连边 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 喵奇葩~哞~咩~
发表于 2020-01-28 14:33:24
链接：https://ac.nowcoder.com/acm/problem/14134来源：牛客网 题目描述𝑅𝑒𝑘𝑖是一名武侦高狙击科的学生，武侦高也设有基础学科，现在她正在完成生物课的作业。给出一张𝑛个点𝑚条边的无向图，这张无向图描述了一个细胞，细胞有三种：X型、Y型还是I型。 如图 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客680645057号
发表于 2020-08-01 02:38:46
/** * 给出一张𝑛个点𝑚条边的无向图，这张无向图描述了一个细胞，细胞有 * 三种：X型、Y型还是I型。 * 思路：1.用数组索引当节点编号（0除外），索引对应的值当作节点有多少条边 * 2.规律：X型有四个顶点，每个 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 正视自己的菜，认清自己的卑微
发表于 2020-12-10 19:52:53
我也不太懂 这是为什么 就讲一下要注意的吧输入时和sum++的数组大小不一样#include<stdio.h>int main (){ int n,m,i,v,u,sum=0; scanf("%d %d",&n,&m); int li[500]={ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 张广文
发表于 2020-03-19 16:08:32
include <bits/stdc++.h> using namespace std;int deg[505];int Hash[505];int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i& 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

枚举
上传者：牛客301599号
难度：
0条回答 2浏览

热门推荐

通过挑战的用户

查看代码

相关试题

生物课程

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号