文档章节

【DFS】CODE[VS] 2066 三角恋(刷题记录)

Fograin
 Fograin
发布于 2016/11/02 12:26
字数 271
阅读 5
收藏 0

点击进入异世界


当时国庆tyvj上面比赛中的一道题,其实是一道tarjan,但可以用dfs来找环

找环就行了,虽然题目让找的是三角恋,但其实只要在有向图中找到环就可以了,因为在一个有向环中,关系是可以传递的,同时符合条件(没有)的应该是个有向无环图(topsort性质),完。

代码如下:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>

const int maxn = 2048;

using namespace std;

int t;
int n;
int dist[maxn];
int map[maxn][maxn];
bool pd;
string sth;

inline void dfs(int x)
{
    for(int i = 1;i <= n;i++)
    {
        if(pd == 1)
            break;
        if(map[x][i] == 1)
        {
            if(dist[i] == -1||dist[i] == 0)
            {
                if(dist[i] == -1)
                {
                    pd = 1;
                    return ;
                }
                dist[i] = -1;
                dfs(i);
            }
        }
    }
dist[x] = 1;    
}

int main()
{
    scanf("%d",&t); 
    for(int k = 1;k <= t;k++)
    {
        memset(map,0,sizeof(map));
        memset(dist,0,sizeof(dist));
        scanf("%d",&n);
        for(int i = 1;i <= n;i++)
        {
            cin>>sth;
            for(int j = 1;j <= n;j++)
            {
                map[i][j] = sth[j-1]-'0';
            }
        }
        pd = 0;
        dist[1] = -1;
        dfs(1);
        if(pd == 1)
            printf("Yes\n");
        else
            printf("No\n"); 
    }

return 0;
}

THE END

By Peacefuldoge

http://blog.csdn.net/loi_peacefuldog

© 著作权归作者所有

Fograin
粉丝 0
博文 22
码字总数 16052
作品 0
莱芜
程序员
私信 提问
程序员跳槽面试刷题必备,微软工程师放大招!| 程序员硬核评测

整理 | 一一 出品 | AI科技大本营(ID:rgznai100) 春节刚过,年终奖收入囊中,属于工程师们一年一度的跳槽季也来了。 跳槽后薪水翻倍自然爽歪歪,但最怕的是面试翻车,那就悲剧了。可想而知...

CSDN资讯
02/19
0
0
帅气中国小哥出“大招”,程序员跳槽面试刷题必备

整理 | 一一 出品 | AI科技大本营 春节刚过,年终奖收入囊中,属于工程师们一年一度的跳槽季也来了。 跳槽后薪水翻倍自然爽歪歪,但最怕的是面试翻车,那就悲剧了。可想而知,想要跳槽或者为...

AI科技大本营
02/18
0
0
2018年用这5种方法提高你的编程实力,学编程就是学手艺!

2017年即将结束了,作为一名程序员,你的技术和能力提高了吗? 面对即将到来的2018年,程序员需要设置一些目标,完成一些挑战。 2018年用这5种方法提高你的编程实力,学编程就是学手艺! 今天...

W3Cschool
2017/12/28
0
0
Arranging Your Team HDU - 3720 【DFS】

思路 题意:此题大意是指首先给你23个队员的信息,包括他们的名字,能力值,在赛场上的职位。然后给出几个若能满足某两个队员同时在球场上就额外加上一定的值。最后让你从23个队员中选出11个...

KeepZ
08/17
0
0
[hdu4609]3-idiots(快速傅利叶变换FFT)

题目名字是三个制杖… 【题意】 有T组数据 每组数据给出n条线段,问任意取三条,可以组成三角形的概率 【输入】 开头一行输入T(T<=10) 下来T组数据,每组数据第一行输入一个n(3<=n<=10^5)...

CABI_ZGX
2017/12/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

前端技术之:Prisma Demo服务部署过程记录

安装前提条件: 1、已经安装了docker运行环境 2、以下命令执行记录发生在MackBook环境 3、已经安装了PostgreSQL(我使用的是11版本) 4、Node开发运行环境可以正常工作 首先需要通过Node包管...

popgis
今天
5
0
数组和链表

数组 链表 技巧一:掌握链表,想轻松写出正确的链表代码,需要理解指针获引用的含义: 对指针的理解,记住下面的这句话就可以了: 将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指...

code-ortaerc
今天
4
0
栈-链式(c/c++实现)

上次说“栈是在线性表演变而来的,线性表很自由,想往哪里插数据就往哪里插数据,想删哪数据就删哪数据...。但给线性表一些限制呢,就没那么自由了,把线性表的三边封起来就变成了栈,栈只能...

白客C
今天
42
0
Mybatis Plus service

/** * @author beth * @data 2019-10-20 23:34 */@RunWith(SpringRunner.class)@SpringBootTestpublic class ServiceTest { @Autowired private IUserInfoService iUserInfoS......

一个yuanbeth
今天
5
0
php7-internal 7 zval的操作

## 7.7 zval的操作 扩展中经常会用到各种类型的zval,PHP提供了很多宏用于不同类型zval的操作,尽管我们也可以自己操作zval,但这并不是一个好习惯,因为zval有很多其它用途的标识,如果自己...

冻结not
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部