2833 奇怪的梦境

题目描述 Description

Aiden陷入了一个奇怪的梦境:他被困在一个小房子中,墙上有很多按钮,还有一个屏幕,上面显示了一些信息。屏幕上说,要将所有按钮都按下才能出去,而又给出了一些信息,说明了某个按钮只能在另一个按钮按下之后才能按下,而没有被提及的按钮则可以在任何时候按下。可是Aiden发现屏幕上所给信息似乎有矛盾,请你来帮忙判断。

输入描述 Input Description

第一行,两个数N,M,表示有编号为1...N这N个按钮,屏幕上有M条信息。

接下来的M行,每行两个数ai,bi,表示bi按钮要在ai之后按下。所给信息可能有重复,保证ai≠bi。

输出描述 Output Description

若按钮能全部按下,则输出“o(∩_∩)o”。

若不能,第一行输出“T_T”,第二行输出因信息有矛盾而无法确认按下顺序的按钮的个数。输出不包括引号。

样例输入 Sample Input

3 3

1 2

2 3

3 2

样例输出 Sample Output

T_T

2

数据范围及提示 Data Size & Hint

对于30%的数据,保证0<N≤100。

对于50%的数据,保证0<N≤2000。

对于70%的数据,保证0<N≤5000。

对于100%的数据,保证0<N≤10000,0<M≤2.5N。

分类标签 Tags 点此展开

裸拓扑

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<stack>
 6 using namespace std;
 7 const int MAXN=30001;
 8 struct node
 9 {
10     int u;
11     int v;
12     int w;
13     int next;
14 }edge[MAXN];
15 int num=1;
16 int head[MAXN];
17 int rudu[MAXN];
18 int tot=0;
19 int n,m;
20 stack<int>s;
21 void topsort()
22 {
23     for(int i=1;i<=n;i++)
24     {
25         if(rudu[i]==0)
26         {
27             s.push(i);
28             tot++;
29         }
30     }
31     while(s.size()!=0)
32     {
33         int p=s.top();
34         s.pop();
35         for(int i=head[p];i!=-1;i=edge[i].next)
36         {
37             rudu[edge[i].v]--;
38             if(rudu[edge[i].v]==0)
39             {
40                 s.push(edge[i].v);
41                 tot++;
42             }
43         }
44     }
45     if(tot==n)printf("o(∩_∩)o");
46     else
47     {
48         printf("T_T\n%d",n-tot);
49         //printf("%d",tot);
50     }
51 }
52 int main()
53 {
54     
55     scanf("%d%d",&n,&m);
56     for(int i=1;i<=n;i++)head[i]=-1;
57     for(int i=1;i<=m;i++)
58     {
59         scanf("%d%d",&edge[num].u,&edge[num].v);
60         edge[num].next=head[edge[num].u];
61         rudu[edge[num].v]++;
62         head[edge[num].u]=num++;
63     }
64     topsort();
65     return 0;
66 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HTML5学堂

DOCTYPE 文档类型

HTML5学堂:在HTML版本从4.0升级到5.0之后,可以采用<!doctype html>这种最新的文档声明方式,那么以前4.0版本,我们也应当有所了解,主...

3136
来自专栏Golang语言社区

golang(Go语言) byte/[]byte 与 二进制形式字符串 互转

效果 把某个字节或字节数组转换成字符串01的形式,一个字节用8个”0”或”1”字符表示。比如: byte(3) –> “00000011” []byte{1...

4957
来自专栏飞雪无情的博客

Go语言实战笔记(二十六)| Go unsafe 包之内存布局

unsafe,顾名思义,是不安全的,Go定义这个包名也是这个意思,让我们尽可能的不要使用它,如果你使用它,看到了这个名字,也会想到尽可能的不要使用它,或者更小心...

802
来自专栏阿凯的Excel

自定义单元格格式(判断版)

前两期分别介绍了自定义单元格格式的数字版、文本版。本期将分享最后一个内容,自定义单元格格式的条件判断。同时也会分享一些比较偏,比较少用的应用! 一、基础知识分...

2914
来自专栏HTML5学堂

2016.05 第三周 群问题分享

HTML+CSS 一个div里面有个img标签,div的高度由img撑开;img的兄弟级有个div要使内层div的高度等于外层div的高度,除了用JS实现,还能...

36813
来自专栏禅林阆苑

Vue2.5源码阅读笔记02—虚拟DOM的创建与渲染

Vue是数据驱动的MVVM框架,视图是由数据驱动生成的,因此对视图的修改不是通过操作 DOM,而是通过修改数据,相比传统使用jQuery的前端开发,能够大大简化...

1.3K77
来自专栏Golang语言社区

如何理解 golang nil

golang 中的 nil 是不同于其他语言的,为了更好的理解 nil,在此我将尝试一步一步揭示 nil 在 golang 中的一些操作和现象。 1. nil ...

3355
来自专栏数据结构与算法

2833 奇怪的梦境 未AC

2833 奇怪的梦境 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description Aide...

2835
来自专栏HTML5学堂

JS简单页面交互实战 - 点击按钮实现求和功能

上一期堡堡给大家讲解了简单的页面交互效果 - 点击块,让块动起来,让我们更清晰的了解JS逻辑和DOM的结合。如果想具体了解点击块,让块动起来,可以回复“交互”到...

5028
来自专栏Google Dart

AngularDart4.0 指南- 模板语法一 顶

学习如何编写显示数据并在数据绑定的帮助下使用用户事件的模板。 Angular应用程序管理用户看到和可以做的事情,通过组件类实例(组件)和面向用户的模板的交互来...

1441

扫码关注云+社区

领取腾讯云代金券