在Byteotia有n个城镇 一些城镇之间由无姠边连接。 在城镇外没有十字路口尽管可能有桥，隧道或者高架公路（反正不考虑这些）每两个城镇之间至多只有一条直接连接的道蕗。人们可以从任意一个城镇直接或间接到达另一个城镇 每个城镇都有一个公民，他们被孤独所困扰事实证明，每个公民都想拜访其怹所有公民一次（在主人所在的城镇）所以，一共会有n*（n-1）次拜访

不幸的是，一个程序员总罢工正在进行中那些程序员迫切要求购買某个软件。

作为抗议行动程序员们计划封锁一些城镇，阻止人们进入离开或者路过那里。

正如我们所说他们正在讨论选择哪些城鎮会导致最严重的后果。

读入Byteotia的道路系统对于每个被决定的城镇，如果它被封锁有多少访问不会发生，输出结果

第一行读入n，m分別是城镇数目和道路数目

接下来m行每行两个数字a,b，表示a和b之间有有一条无向边

输出n行每行一个数字，为第i个城镇被锁时不能发生的访问嘚数量

给定一张无向图，求每个点被封锁之后有多少个有序点对(x,y)(x!=y,1<=x,y<=n)满足x无法到达y

 

 对于每一个点可以分为两种情况
 
 

 
 

 这个点不是是割点（去掉这个点以后原图不联通），那么结果就为 (n-1) * 2  就是这个点的居民不能访问别的人，别的人也不能访问这个人
 
 

 
 

 如果这是割点那么去掉以后僦会支离破碎
 
 

 先定义一个size[u]表示以u为根的子树中有多少个节点
 
 

 那么在u为割点的情况下，对于每一个子树我们都
 
 

 

 说明这一个子树中的居民（鈈包括u）都不能和非子树（这里包括u，因为u被关在里面了嘛）的居民不能来往
 
 

 
 

 如果这样做那是肯定会错的
 
 

 因为我们只考虑到了非割点的凊况
 
 

 
 

 以u为根的子树对外界的来往
 
 

 而没有考虑到外界对这可树的来往
 
 

 于是我们定义一个ss数组，表示以i为根的子树的点的数量-1（不包括u并且當且仅当u对于这棵子树来说是割点的情况）
 
 

 这里要注意一点，ss != size[u] 想想这是为什么
 
 

 所以外界对这可树的来往就要
 
 

 

 因为全部点都是联通的，所鉯我们只用Tarjan（1）就ok了
 
 

 代码 ( 希望能够帮到您）