TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4091
  • 题目
  • P4091舞会
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1s
    问题描述

         约翰的N(2≤N≤10000)只奶牛非常兴奋,因为这是舞会之夜!她们穿上礼服和新鞋子,别上鲜花,她们要表演圆舞.

        只有奶牛才能表演这种圆舞.圆舞需要一些绳索和一个圆形的水池.奶牛们围在池边站好,顺时针顺序由1到N编号.每只奶牛都面对水池,这样她就能看到其他的每一只奶牛.为了跳这种圆舞,她们找了M(2≤M≤50000)条绳索.若干只奶牛的蹄上握着绳索的一端,绳索沿顺时针方绕过水池,另一端则捆在另一些奶牛身上.这样,一些奶牛就可以牵引另一些奶牛.有的奶牛可能握有很多绳索,也有的奶牛可能一条绳索都没有。
          对于一只奶牛,比如说贝茜,她的圆舞跳得是否成功,可以这样检验:沿着她牵引的绳索,按顺时针方向,找到她牵引的奶牛,再沿着这只奶牛牵引的绳索,又找到一只被牵引的奶牛,如此下去,若最终能回到贝茜,则她的圆舞跳得成功,如果这样的检验无法完成,那她的圆舞是不成功的.

         如果两只成功跳圆舞的奶牛有绳索相连,那她们可以同属一个组.

         给出每一条绳索的描述,请找出,成功跳了圆舞的奶牛有多少个组(要求一组至少有两头奶牛)?

    输入格式

    第1行输入N和M,
    接下来M行每行两个整数A和B,表示沿顺时针方向A牵引着B.

    输出格式

    一个整数,表示成功跳圆舞的奶牛组数.

    样例输入 1

    5 4
    2 4
    3 5
    1 2
    4 1

    样例输出 1

    1

    样例输入 2

    9 20
    1 6
    9 6
    3 4
    4 3
    5 6
    6 7
    7 8
    5 1
    9 5
    8 7
    5 9
    9 8
    9 1
    8 1
    1 5
    6 1
    8 5
    1 9
    7 5
    7 6

    样例输出 2

    2

    提示

    样例说明:
    1,2,4这三只奶牛同属一个成功跳了圆舞的组.而3,5两只奶牛没有跳成功的圆舞

     


    来源  usaco 2006 jan