首页 > 代码库 > 2833 奇怪的梦境

2833 奇怪的梦境

2024-09-15 07:22:18   222人阅读

题目描述 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     else47     {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 }

 

2833 奇怪的梦境


联系
我们