首页 > 其他分享 >105 判断图是否同构

105 判断图是否同构

时间:2024-08-14 10:53:00浏览次数:13  
标签:输出 同构 判断 int include 号点 105

// 105 判断图是否同构.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
http://oj.daimayuan.top/course/14/problem/600

给你两张无向简单图,保证两张图的顶点数和边数相同,请判断这两张图是否同构。

如果同构输出 Yes,否则输出 No。

输入格式
第一行两个整数 n,m,表示图的顶点数和边数,顶点编号从 1到 n。

接下来 m行描述第一张图,每行两个整数 x,y,表示 x号点和 y号点之间有一条边。

再接下来 m行描述第二张图,每行两个整数 x,y,表示 x号点和 y号点之间有一条边。

输出格式
输出一行一个字符串,表示答案。

样例输入
3 2
1 2
2 3
1 3
2 3
样例输出
Yes
数据规模
对于所有数据,保证 1≤n≤8,0≤m≤n(n−1)/2,1≤x,y≤n。
*/


#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <unordered_map>

using namespace std;

const int N = 10;
int g[N][N];
int t[N][N];
int vis[N];
unordered_map<int, int> mm;
int n, m;

bool dfs(int x,int y) {
	vis[y] = 1; mm[x] = y;

	if (x == n) {
		//检查
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (g[i][j] != t[mm[i]][mm[j]]) {
					vis[y] = 0; mm[x] = 0;
					return false;
				}
			}
		}
		return true;
	}

	for (int i = 1; i <= n; i++) {
		if (vis[i] == 1) continue;
		if (dfs(x + 1, i)) {
			return true;
		}
	}
	vis[y] = 0; mm[x] = 0;

	return false;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b; cin >> a >> b; g[a][b] = 1; g[b][a] = 1;
	}
	for (int i = 1; i <= m; i++) {
		int a, b; cin >> a >> b; t[a][b] = 1; t[b][a] = 1;
	}

	for (int i = 1; i <= n; i++) {
		if (dfs(1, i)) {
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;

	return 0;
}

标签:输出,同构,判断,int,include,号点,105
From: https://www.cnblogs.com/itdef/p/18358409

相关文章

  • C#判断程序是由Windows服务启动还是用户启动
       在Windows系统做网络开发,很多时候都是使用Windows服务的模式,但在调度阶段,我们更多的是使用控制台的模式。在开发程序的时候,我们在Program的Main入口进行判断。最初开始使用Environment.UserInteractive属性,在系统不系统服务的交互模式时,程序运行是正常的,但试过有Win7下,......
  • Js if 判断 for循环
    三大结构顺序结构:从上到下执行分支结构:选择性执行循环结构:重复执行什么是流程分支结构?条件控制(逻辑分支),就是根据我们设定好的条件来控制程序执行的方式,JavaScript提供了很多控制语法,目前我们先学习使用一种:if()else基本语法语法1-if语句单分支//基本语法:if......
  • 盘点两种方法来判断一个列表里面,按关键词进行筛选,留下包含有关键词的论文题目
    大家好,我是Python进阶者。前言前几天才哥群里有个粉丝提问,忘记是谁了,过去有段时间,当时没来得及截图,不知道谁问的了,不过题目当时记下来了,如下图所示。看上去并不是很难的样子,这个示例代码,看上去逻辑什么的也没有问题,但是结果输出就是有些不对。究其原因,因为title里边是列表,而不......
  • 痞子衡嵌入式:探析i.MXRT1050在GPIO上增加RC延时电路后导致边沿中断误触发问题(上篇)
    大家好,我是痞子衡,是正经搞技术的痞子。今天痞子衡给大家分享的是i.MXRT1050在GPIO上增加RC延时电路后导致边沿中断误触发问题探析。前段时间有一个RT1052客户反馈了一个有趣的问题,他们设计得是一个带LCD屏交互的应用,应用以官方SDK里的lvgl_demo_widgets_bm例程......
  • 最高法--未交付未结算与未交付已结算的工程优先受偿权的判断
    (2021)最高法民申7378号  威海经济技术开发区北港房地产开发中心、中建海峡建设发展有限公司建设工程施工合同纠纷民事申请再审审查民事裁定书申请人主张:4.一二审法院未正确适用《最高人民法院关于审理建设工程施工合同纠纷案件适用法律问题的解释(二)》第十八条的规定,错误认定应......
  • JAVA实现判断小程序用户是否关注公众号
    本文主要描述了判断小程序用户是否关注公众号的逻辑实现及部分代码首先阐述一下大致流程:1、在将小程序和公众号绑定至同一个微信开发平台下;2、后端拉取公众号已关注用户列表,并获取其中每一个用户的unionID,建立已关注用户表;3、后端可做定时任务更新该表;4、用户在小程序中......
  • 超简单适合练手的双指针题:判断子序列
    给定字符串 s 和 t ,判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。示例1:输入:s="abc",t="ahbgdc"输出:true示例2:输入:s="axc......
  • String类中的判断方法 day11
    packagecom.shujia.day11;/*String类中的判断功能:booleanequals(Objectobj)String类中的equals是重写父类Object中的equals方法,比较的是内容booleanequalsIgnoreCase(Stringstr)忽略大小写比较字符串内容booleancontains(Strin......
  • C++竞赛初阶L1-10-第四单元-if练习(第24课)100015: 判断能否被 3,5,7 整除
    题目内容给定一个整数 x,判断它能否被 3,5,7 整除,并输出以下信息:1、能同时被 3,5,7 整除(直接输出 357,每个数中间一个空格);2、只能被其中两个数整除(按从小到大的顺序输出两个数,例如:35 或者 37 或者 57,中间用空格分隔);3、只能被其中一个数整除(输出这个除数);4、不能......
  • 编写类 AA ,有一个方法:判断一个数是奇数 odd 还是偶数, 返回 boolean
    1publicclassMethodExercise01{2publicstaticvoidmain(String[]args){34AAa=newAA();5if(a.isOdd(2)){//T,这样的写法以后会看到很多6System.out.println("是奇数");78}else{9System.o......