图的割点与割边学习笔记

wamaker posted @ 2010年9月21日 02:54 in 图论 with tags 割点，割边 , 3898 阅读

 

割点

割点：如果在图G中删去一个结点u后，图G的连通分枝数增加，即W(G-u)>W(G)，则称结点u为G的割点，又称关节点。
     直观地说，就是删除了连通图的某点后，图不在连通，而是分为几个连通分量。

性质：（1）考虑根节点Root，如果Root有数量多于1的子结点时，Root是割点。

      （2）考虑非根结点u，当且仅当u的某个儿子及儿子的子孙均没有指向u的祖先的后向边时，u是割点。（LOW[v]>=DFN[u],v是u的孩子）

代码：

 

void DFS(int cur,int par)
 {
     dfn[cur]=low[cur]=++Index;
     
     int size=adj[cur].size();
     int cnt=0;
     for(int i=0;i<size;i++)
     {    
         int v=adj[cur][i];
         if(!dfn[v])
         {
             cnt++;
             DFS(v,cur);
             if(low[cur]>low[v])
                 low[cur]=low[v];
             if((cur==root&&cnt==2)||(cur!=root&&low[v]>=dfn[cur]))
                 flag[cur]=true;
         }
         else if(v!=par&&low[cur]>dfn[v])
             low[cur]=dfn[v];
     }
 }

 

割边

割边：如果在图G中删去一条边e后，图G的连通分支数增加，即W(G-e)>W(G)，则称边u为G的桥，又称割边或关节边。

 性质: 对于一条边<u,v>，v是u的孩子如果儿子及儿子的子孙均没有指向u的祖先的后向边时，<u,v>是割边。（LOW[v]>DFN[u]）

代码：

 

void CutEdge(int cur,int par)
 {    dfn[cur]=low[cur]=++Index;
     
      for(int i=head[cur];i;i=buf[i].next)
     {
         int v=buf[i].v;
         if(v==par)continue;
         if(!dfn[v])
         {
             CutEdge(v,cur);
             if(low[cur]>low[v])
                 low[cur]=low[v];
             if(low[v]>dfn[cur])
             {    
                     ans[nAns++]=buf[i].id;
             }
         }
         else if(low[cur]>dfn[v])
             low[cur]=dfn[v];
     }
 }

 

相关习题：

POJ 1144 Network 赤果果的求割点的题。

相关链接:
Beyond the Void的讲解，很精彩

推荐阅读：

lrj的黑书P285

  • 无匹配
Small_feed 评论 (38)
2
[回复]
Avatar_small
netflix tv8 说:
2023年7月15日 00:26

Netflix propose une gamme de films, d’émissions de télévision et de contenus originaux pour un abonnement mensuel raisonnable. Netflix peut être vu sur Smart TV, un appareil de diffusion en continu ou un système de jeu moderne doté d’une connectivité Internet. netflix tv8 Certains appareils nécessitent que vous activiez l’appareil avant de vous connecter. Ceci est habituel avec les nouveaux appareils ou ceux qui viennent de recevoir des modifications logicielles.

3
[回复]
Avatar_small
NCERT 9th Exemplar 说:
2023年8月24日 13:34

Exemplar Problems and Solutions Required for CBSE Exam, as well as useful to form the Foundation in the NCERT Examination, Students Download the latest NCERT Exemplar Problems Class 9 in Pdf Format, in both Hindi and English. Urdu Medium You can also buy them from the links given.Our website we are Providing the NCERT 9th for all Chapters of class All the Questions are NCERT 9th Exemplar Problem 2024 very Important for the Upcoming class Exam, All the NCERT Class Exemplar Solutions 2024 for English, Hindi, Mathematics, Sanskrit, Science, Social Science, Urdu have been Explained in a way to help Students Thoroughly Understand the concept

4
[回复]
Avatar_small
메이저사이트 说:
2024年4月29日 14:42

I'm incredibly burnt out on attempting to find key and sharp talk concerning this. Outline our site, and we will find you.

5
[回复]
Avatar_small
토토사이트 说:
2024年4月29日 14:43

There is so much in this article that I would never have thought of on my own.  Your content gives readers things to think about in an interesting way.  Thank you for your clear information.

6
[回复]
Avatar_small
토토사이트홍보 说:
2024年4月29日 14:44

This method is actually aesthetically truly the most suitable. Every one associated with tiny illustrates tend to be meant by way of numerous history abilities. I suggest the program quite a bit.

7
[回复]
Avatar_small
토토사이트 说:
2024年4月29日 14:44

Yes, great US Military force. Also, in his post you have given a chance to listen about US Military. I really appreciate your work. Thanks for sharing it.

8
[回复]
Avatar_small
먹튀검증업체 说:
2024年4月29日 14:45

When your website or blog goes live for the first time, it is exciting. That is until you realize no one but you and your

9
[回复]
Avatar_small
먹튀뱅크 说:
2024年4月29日 14:45

When your website or blog goes live for the first time, it is exciting. That is until you realize no one but you and your

10
[回复]
Avatar_small
검증사이트 说:
2024年4月29日 15:35

This is very interesting content! I have thoroughly enjoyed reading your points and have come to the conclusion that you are right about many of them. You are great.

11
[回复]
Avatar_small
퍼스트카지노 说:
2024年4月29日 15:37

Tinned copper flat wire are widely used in the solar power industry as interconnect ribbons which are soldered onto the silicon cell – take away the energy produced photoelectrically. The connection of these interconnect ribbons with the rectifier takes place via the so-called busbars – slightly larger copper ribbons that are also tinned.

12
[回复]
Avatar_small
토토사이트종류 说:
2024年4月29日 15:37

I just found this blog and have high hopes for it to continue. Keep up the great work, its hard to find good ones. I have added to my favorites. Thank You.

13
[回复]
Avatar_small
메이저놀이터 说:
2024年4月29日 15:38

Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!Thanks

14
[回复]
Avatar_small
먹튀검증 说:
2024年4月29日 15:39

Regular visits listed here are the easiest method to appreciate your energy, which is why why I am going to the website everyday, searching for new, interesting info. Many, thank you!

15
[回复]
Avatar_small
먹튀제보 说:
2024年4月29日 15:39

Thanks for posting this info. I just want to let you know that I just check out your site and I find it very interesting and informative. I can't wait to read lots of your posts.

16
[回复]
Avatar_small
먹튀폴리스주소 说:
2024年4月29日 18:22

The bleach blond rapper may have been shooting the music video for her new single "High School," but that didn't stop her from going for a decidedly more grown-up look as she took the plunge in a shocking neon yellow swimsuit that barely managed to cover up her ample assets.

17
[回复]
Avatar_small
토크리 说:
2024年4月29日 18:23

This program seems to be tailored to cater to individuals who might face challenges in accessing traditional mental health services. By focusing on mild to moderate mental illness, it suggests that the program aims to address a range of mental health conditions within a specific severity spectrum.

18
[回复]
Avatar_small
온라인카지노 说:
2024年4月29日 18:23

When your website or blog goes live for the first time, it is exciting. That is until you realize no one but you and your

19
[回复]
Avatar_small
토동산 说:
2024年4月29日 18:24

When your website or blog goes live for the first time, it is exciting. That is until you realize no one but you and your

20
[回复]
Avatar_small
먹튀검증 说:
2024年4月29日 18:24

I'm incredibly burnt out on attempting to find key and sharp talk concerning this. Outline our site, and we will find you.

21
[回复]
Avatar_small
검증나라 说:
2024年4月29日 18:25

Good composed article. It will be steady to any individual who uses it, including me. Continue doing what you are doing – can'r hold up to peruse more posts.

22
[回复]
Avatar_small
ok토토먹튀검증 说:
2024年4月29日 18:26

I just found this blog and have high hopes for it to continue. Keep up the great work, its hard to find good ones. I have added to my favorites. Thank You.

23
[回复]
Avatar_small
꽁머니 说:
2024年4月29日 18:27

You completed a number of nice points there. I did a search on the issue and found nearly all people will have the same opinion with your blog.

24
[回复]
Avatar_small
먹튀검증 说:
2024年4月29日 18:29

Good composed article. It will be steady to any individual who uses it, including me. Continue doing what you are doing – can'r hold up to peruse more posts.

25
[回复]
Avatar_small
코인카지노 说:
2024年4月29日 18:30

I'm incredibly burnt out on attempting to find key and sharp talk concerning this. Outline our site, and we will find you.

26
[回复]
Avatar_small
토토사이트 说:
2024年4月29日 18:31

This is very interesting content! I have thoroughly enjoyed reading your points and have come to the conclusion that you are right about many of them. You are great.

27
[回复]
Avatar_small
메이저사이트 说:
2024年4月29日 18:32

What a fantabulous post this has been. Never seen this kind of useful post. I am grateful to you and expect more number of posts like these. Thank you very much.

28
[回复]
Avatar_small
메이저사이트 说:
2024年4月29日 18:33

Thank you for sharing this informative article. I am very interested in the information you have shared

29
[回复]
Avatar_small
토토사이트검증 说:
2024年4月29日 18:33

The group has struggled to carry out planned sales due topolitical opposition to foreign takeovers at a time when aprotracted economic crisis has forced many Italian entrepreneursto put their businesses on the block.

30
[回复]
Avatar_small
먹튀개구리 说:
2024年4月29日 18:34

This method is actually aesthetically truly the most suitable. Every one associated with tiny illustrates tend to be meant by way of numerous history abilities. I suggest the program quite a bit.

31
[回复]
Avatar_small
온라인카지노추천 说:
2024年4月29日 18:35

Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!Thanks

32
[回复]
Avatar_small
안전카지노사이트 说:
2024年4月29日 18:37

This is my first time i visit here. I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here keep up the good work

33
[回复]
Avatar_small
메이저토토사이트 说:
2024年4月29日 18:38

Positive site, where did u come up with the information on this posting? I'm pleased I discovered it though, ill be checking back soon to find out what additional posts you include.

34
[回复]
Avatar_small
คาสิโน 说:
2024年4月29日 18:38

What a fantabulous post this has been. Never seen this kind of useful post. I am grateful to you and expect more number of posts like these. Thank you very much.

35
[回复]
Avatar_small
토토사이트실험실 说:
2024年4月29日 18:39

An impressive share! I have just forwarded this onto a co-worker who has been doing a little research on this.

36
[回复]
Avatar_small
먹튀검증 说:
2024年4月29日 18:46

What a fantabulous post this has been. Never seen this kind of useful post. I am grateful to you and expect more number of posts like these. Thank you very much.

37
[回复]
Avatar_small
먹튀타운 说:
2024年4月29日 18:47

An impressive share! I have just forwarded this onto a co-worker who has been doing a little research on this.

38
[回复]
Avatar_small
먹튀검증커뮤니티 说:
2024年4月29日 18:47

Hey, I just hopped over to your site via StumbleUpon.  Not somthing I would normally read, but I liked your thoughts none the less.  Thanks for making something worth reading.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter