CSU1660: K-Cycle
Description
A simple cycle is a closed simple path, with no other repeated vertices or edges other than the starting and ending vertices. The length of a cycle is the number of vertices on it. Given an undirected graph G(V, E), you are to detect whether it contains a simple
cycle of length K. To make the problem easier, we only consider cases with small K here.
Input
There are multiple test cases.
The first line will contain a positive integer T (T ≤ 10) meaning the number of test cases.
For each test case, the first line contains three positive integers N, M and K ( N ≤ 50, M ≤ 500, 3 ≤ K ≤ 7). N is the number of vertices of the graph, M is the number of edges and K is the length of the cycle desired. Next follow M lines, each line contains
two integers A and B, describing an undirected edge AB of the graph. Vertices are numbered from 0 to N-1.
Output
For each test case, you should output “YES” in one line if there is a cycle of length K in the given graph, otherwise output “NO”.
Sample Input
2
6 8 4
0 1
1 2
2 0
3 4
4 5
5 3
1 3
2 4
4 4 3
0 1
1 2
2 3
3 0
Sample Output
YES
NO
HINT
Source
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <list>
#include <algorithm>
#include <climits>
using namespace std; #define lson 2*i
#define rson 2*i+1
#define LS l,mid,lson
#define RS mid+1,r,rson
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define N 200005
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define lowbit(x) (x&-x)
const int mod = 1e9+7;
vector<int> a[550];
int vis[550],flag;
int n,m,k; void dfs(int now,int pos,int pre)
{ if(vis[now])
{
if(pos-vis[now]==k)
flag = 1;
return;
}
if(flag)
return;
vis[now]=pos;
int i,len = a[now].size();
for(i = 0; i<len; i++)
{
if(a[now][i]!=pre)
dfs(a[now][i],pos+1,now); }
} int main()
{
int i,j,x,y,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
for(i = 0; i<=n; i++)
a[i].clear();
flag = 0;
while(m--)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
for(i=0; i<n; i++)
{
MEM(vis,0);
dfs(i,1,-1);
}
printf("%s\n",flag?"YES":"NO");
} return 0;
}
最新文章
- Xamarin Android教程Android基本知识版本介绍与系统介绍
- MySQL表类型和存储引擎版本不一致解决方法
- php strcmp引起的问题
- 整合spring roo,maven,mybatis,spring-flex,blazeds,mysql
- centos使用denyhosts的问题,会将自己的IP自动加到hosts.deny的解决办法。
- 常用CentOS 6/7 扩展源
- Android+OpenCV 摄像头实时识别模板图像并跟踪
- 求a,b在区间上的公倍数个数
- Linux系统学习笔记:文件I/O
- There is no getter for property named xxx&#39; in &#39;class java.lang.xxx&#39;
- C#中简单的this与get的用法(string,decimal)
- js 实现div模块的截图并下载功能(可制作长图)
- MySQL InnoDB四个事务级别 与 脏读、不反复读、幻读
- 转载iOS开发中常见的警告及错误
- 应用调试(四)系统调用SWI
- 【noip 2012】提高组Day2T3.疫情控制
- angular组件之间的通讯
- 基于OpenGL编写一个简易的2D渲染框架-10 重构渲染器-Pass
- 基于UML的毕业设计管理系统的分析与设计
- Android Library和Android APP、Java Library的区别
热门文章
- SCOPE_IDENTITY()和 SELECT @@IDENTITY 的用法
- java.util.logging.FileHandler
- Yeslab华为安全HCIE七门之--防火墙高级技术(17篇)
- shell的结构化命令
- 两种方法解决 ";The License CNEKJPQZEX- has been cancelled..."; 问题
- 数据库更新DATE类型的时间
- CCF模拟题 窗口
- Windows Server 2016 主域控制器搭建
- POJ 3613 Cow Relays 恰好n步的最短路径
- python学习日记-180823