emm一开始将++cnt敲成cnt++

就很委屈

一个拓扑排序而已

Description

挑竹签——小时候的游戏

　　　夏夜，早苗和诹访子在月光下玩起了挑竹签这一经典的游戏。挑竹签，就是在桌上摆上一把竹签，每次从最上层挑走一根竹签。如果动了其他的竹签，就要换对手来挑。在所有的竹签都被挑走之后，谁挑走的竹签总数多，谁就胜了。身为神明的诹访子自然会让早苗先手。为了获胜，早苗现在的问题是，在诹访子出手之前最多能挑走多少竹签呢？为了简化问题，我们假设当且仅当挑最上层的竹签不会动到其他竹签。

Input

第一行输入两个整数n,m, 表示竹签的根数和竹签之间相压关系数。
第二行到m+1 行每行两个整数u,v，表示第u 根竹签压住了第v 根竹签。

Output

一共一行，一个整数sum，表示最多能拿走sum 根竹签。

Sample Input

6 6
1 2
2 3
3 1
4 3
4 5
6 5

Sample Output

3
样例解释：
一共有6 根竹签，其中1 压住2，2 压住3，3 压住1，4 压住3 和5，6 压住5。最优方案中，我们可以依次挑走4、6、5 三根竹签。而剩下的三根相互压住，都无法挑走。所以最多能挑走3 根竹签。

Data Constraint

对于20% 的数据，有1<= n,m<= 20。

　　对于40% 的数据，有1 <= n,m <= 1 000。
　　对于100% 的数据，有1 <= n,m <= 1 000 000。

CODE

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,cnt=;

int head[],in[],so[];

struct node{int to,next;}edge[];

void add(int s,int e)

{

    in[e]++;

    edge[++cnt].to=e;

    edge[cnt].next=head[s];

    head[s]=cnt;

}

int  main()

{

    int i,u,v,cnt=,cntt=,now=,ans=;

    memset(head,-,sizeof(head));

    scanf("%d%d",&n,&m);

    for(i=;i<=m;i++) scanf("%d%d",&u,&v),add(u,v);

    for(i=;i<=n;i++) if (!in[i])so[++cnt]=i;

    while(cntt<=cnt)

    {

        ans++;

        now=so[cntt++];

        for(i=head[now];i!=-;i=edge[i].next)

        {

            in[edge[i].to]--;

            if (!in[edge[i].to]) so[++cnt]=edge[i].to;

        }

    }

    printf("%d\n",ans);

return ;

}

巴特西

<JZOJ4269>挑竹签

emm一开始将++cnt敲成cnt++

就很委屈

一个拓扑排序而已

Description

Input

Output

Sample Input

Sample Output

Data Constraint

CODE

最新文章

热门文章