图论——强连通分量:Tarjan算法——练习1

时间:2023-02-03 20:58:05

上一次我们详细介绍了强连通分量的Tarjan算法,今天呢,我们来做一些习题来巩固Tarjan算法,毕竟它十分重要。

Tarjan算法详解

上面是上一次的详解,在做题时可供参考。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

                              练习一般采用洛谷题库。  

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

T1.  luogu   P2341   受欢迎的牛    来源: HAOI2006

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶

牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜

欢B,B喜欢C,那么A也喜欢C。牛栏里共有N 头奶牛,给定一些奶牛之间的爱慕关系,请你

算出有多少头奶牛可以当明星。

输入输出格式

输入格式:

 

 第一行:两个用空格分开的整数:N和M

 第二行到第M + 1行:每行两个用空格分开的整数:A和B,表示A喜欢B

 

输出格式:

 

 第一行:单独一个整数,表示明星奶牛的数量

 

输入输出样例

输入样例#1: 复制
3 3
1 2
2 1
2 3
输出样例#1: 复制
1

说明

只有 3 号奶牛可以做明星

【数据范围】

10%的数据N<=20, M<=50

30%的数据N<=1000,M<=20000

70%的数据N<=5000,M<=50000

100%的数据N<=10000,M<=50000

 

分析

对于奶牛之间的关系,不难看出,可以用一个有向图表示。奶牛A喜欢奶牛B,则转化为节点A到节点B有一条有向边。

然后,我们再来分析一下样例,并从中找到解题方法,解题思路。

 

图论——强连通分量:Tarjan算法——练习1

这,是我们将奶牛之间的关系转化而来的有向图。

图论——强连通分量:Tarjan算法——练习1

不难发现,节点1与节点2形成了强连通分量。我们一看到强连通分量,就要先想到缩点,把问题简单化,不行再想别的方法。

 

图论——强连通分量:Tarjan算法——练习1

这是缩点之后的样子。变成了一个非常简单的图。

那么,接下来怎么办呢?

样例是说只有3号奶牛是“明星”,我们就来看3号奶牛有什么特点。

 

当我们缩完点之后,这个有向无环图(DAG)中,不会再有强连通的两点,于是可以得出两点之间最多只有一条有向路径,也就是不存在两只牛互相喜欢。(我们把构成强连通分量的点看做是一只牛)。

 

这说明什么呢?

 

这说明若一直奶牛是明星,那在缩点之后,它一定不会喜欢任意一头奶牛。这在有向图中叫出度为0。也就是说它没有去别的节点的路径。

如果缩点之后一个由强连通分量组成的节点时明星,则属于这个强连通分量的所有节点都是明星。(他们互相喜欢)。

 

这样一看,题目就变得简单了。

 

解题过程也很明了:

 

1.通过奶牛的关系建立一个有向图。

2.使用Tarjan算法把强连通分量缩成一个点。

3.遍历缩点后的有向图,找出出度为0的节点,加到Ans中去。

4.得解。

 

分析了这么多,大概可以AK了吧。

 

这题思路没有问题,但在一些细节上需要注意,不要掉坑。

接下来开始填坑。

1.100%的数据N<=10000,M<=50000

数据范围:10000点,于是int的二维数组开不下10000^2,所以存图时建议使用vector(不定长数组)或 链式前向星 来存图。

vector存图:大佬的博客

链式前向星存图:大佬的博客

以上两个博客介绍了这两种优秀的存图方法,不会的可以看一看。

2.有一个大佬说:我们只关注一个分量的出度是否为0,所以不用判断两个分量间的边是否重复统计

3.另一个大佬说:数据水

好吧,也就这些了,最后给代码:

code:

 1 #include<bits/stdc++.h>
 2 #define maxn 1000000
 3 using namespace std;
 4 int Next[maxn],a=0,F[maxn],Head[maxn],cmpi[maxn],out[maxn],E[maxn],cmp[maxn],s[maxn],dfn[maxn],low[maxn],top=0,cmpid=0,tim=0;
 5 bool V[maxn],D[maxn];
 6 void ins(int x,int y,int i)
 7 {
 8     E[i]=y;
 9     Next[i]=Head[x];
10     Head[x]=i;
11 }//链式前向星写法,详见博客
12 int find()
13 {
14     int ans=0;
15     for(int i=1;i<=a;i++)
16     {
17         for(int p=Head[F[i]];p;p=Next[p])//列举这个点的所有邻接点
18         {
19             if(!D[E[p]])ans++;//如果这个点的邻接点不和他在一个强联通分量的话,那么我们就发现他所在的分量有了出度
20         }
21     }
22     return ans;
23 }//找一组强连通分量的出度,若为0,下面的答案就累加
24 void tarjan(int u)
25 {
26     dfn[u]=low[u]=++tim;
27     s[++top]=u;
28     V[u]=true;
29     for(int p=Head[u];p;p=Next[p])
30     {
31         int y=E[p];
32         if(!dfn[y])
33         {
34             tarjan(y);
35             low[u]=min(low[y],low[u]);
36         }
37         else
38         {
39             if(V[y])low[u]=min(low[u],dfn[y]);
40         }
41     }
42     if(dfn[u]==low[u])
43     {
44         int y;
45         cmpid++;
46         do
47         {
48             y=s[top--];
49             V[y]=false;
50             F[++a]=y;//将这个点存入暂时数组
51             D[y]=true;
52             cmpi[cmpid]++;
53         }while(y!=u);
54         cmp[cmpid]=find();//cmp存储他的出度
55         a=0;
56         memset(D,false,sizeof(D));//D数组表示这个点在不在这个强连通分量
57     }
58 }//Tarjan算法缩点,模板在我的博客里有
59 int main()
60 {
61     int n,m;
62     scanf("%d%d",&n,&m);
63     for(int i=1;i<=m;i++)
64     {
65         int a,b;
66         scanf("%d%d",&a,&b);
67         ins(a,b,i);//建图
68     }
69     for(int i=1;i<=n;i++)
70        if(!dfn[i])tarjan(i);
71     int c=0,ans;
72     for(int i=1;i<=cmpid;i++)
73       if(!cmp[i])c++,ans=i;//检查图是否连通
74     if(c==1)
75         printf("%d",cmpi[ans]);
76     else 
77         printf("0");
78     return 0;
79 }         

希望大家在不抄题解的情况下能写对代码,多理解,多总结,这对你们帮助很大。

 

好了,今天的讲解就到这里,之后还会有习题分享给大家,我们下次见。