tarjan初探Luogu P2341

tarjan初探Luogu P2341"/>

tarjan初探Luogu P2341

题目传送门

标签： t a r j a n tarjan tarjan求强联通分量

何为强联通分量

有向图强连通分量：在有向图 G G G中，如果两个顶点 V i , V j V_i,V_j Vi​,Vj​间（ V i > V j V_i>V_j Vi​>Vj​）有一条从 V i V_i Vi​到 V j V_j Vj​的有向路径，同时还有一条从 V i V_i Vi​到 V j V_j Vj​的有向路径，则称两个顶点强连通。如果有向图 G G G的每两个顶点都强连通，称 G G G是一个强连通图。有向图的极大强连通子图，称为强连通分量。 ——百度百科

事实上，你大概可以理解为：如果一个图的子图中，任意两点可以相互到达，那么这就组成了一个强联通分量。

如果还不理解怎么办？没关系，我们上图像来理解

如图，在这个有向图中，一共有 { 1 , 2 , 3 , 4 } , { 5 } , { 6 } \{1,2,3,4\},\{5\},\{6\} {1,2,3,4},{5},{6}三个强联通分量

如何求强联通分量

我们需要两个非常重要的数组，在这里先说明一下

1. d f n 1.dfn 1.dfn，表示这个点在 d f s dfs dfs时是第几个被搜到的。

2. l o w 2.low 2.low，表示这个点以及其子孙节点连的所有点中 d f n dfn dfn最小的值

3. s t a c k 3.stack 3.stack，表示当前所有可能能构成是强连通分量的点。

4. v i s 4.vis 4.vis，表示一个点是否在 s t a c k stack stack数组中。

我们使用 t a r j a n tarjan tarjan的方法
(1)、首先初始化 d f n [ u ] = l o w [ u ] = dfn[u]=low[u]= dfn[u]=low[u]=第几个被 d f s dfs dfs到

(2)、将 u u u存入 s t a c k [ ] stack[ ] stack[]中，并将 v i s [ u ] vis[u] vis[u]设为 t r u e true true

(3)、遍历 u u u的每一个能到的点，如果这个点 d f n [ ] dfn[ ] dfn[]为 0 0 0，即仍未访问过，那么就对点 v v v进行 d f s dfs dfs，然后 l o w [ u ] = m i n { l o w [ u ] , l o w [ v ] } low[u]=min\{low[u],low[v]\} low[u]=min{low[u],low[v]}

(4)、假设我们已经 d f s dfs dfs完了 u u u的所有的子树那么之后无论我们再怎么 d f s dfs dfs， u u u点的 l o w low low值已经不会再变了。

至此， t a r j a n tarjan tarjan完美结束

那么如果 d f n [ u ] = l o w [ u ] dfn[u]=low[u] dfn[u]=low[u]这说明了什么呢？

再结合一下 d f n dfn dfn和 l o w low low的定义来看看吧

d f n dfn dfn表示 u u u点被 d f s dfs dfs到的时间， l o w low low表示 u u u和 u u u所有的子树所能到达的点中 d f n dfn dfn最小的。

这说明了 u u u点及 u u u点之下的所有子节点没有边是指向u的祖先的了，即我们之前说的 u u u点与它的子孙节点构成了一个最大的强连通图即强连通分量

此时我们得到了一个强连通分量，把所有的u点以后压入栈中的点和u点一并弹出，将它们的 v i s [ ] vis[ ] vis[]置为 f a l s e false false，如有需要也可以给它们打上相同标记（同一个数字）

Q : Q: Q: d f n dfn dfn可以理解，但为什么 l o w low low也要这么做呢？

A : A: A:因为low的定义如上，也就是说如果没有子孙与u的祖先相连的话， d f n [ u ] dfn[u] dfn[u]一定是它和它的所有子孙中 d f n dfn dfn最小的（因为它的所有子孙一定比他后搜到）。

Q : Q: Q: s t a c k [ ] stack[] stack[]有什么用？

A : A: A:如果 u u u在 s t a c k stack stack中， u u u之后的所有点在 u u u被回溯到时 u u u和栈中所有在它之后的点都构成强连通分量。

Q : Q: Q: l o w [ ] low[ ] low[]有什么用？

A : A: A:应该能看出来吧，就是记录一个点它最大能连通到哪个祖先节点（当然包括自己）

如果遍历到的这个点已经被遍历到了，那么看它当前有没有在 s t a c k [ ] stack[ ] stack[]里,如果有那么 l o w [ u ] = m i n { l o w [ u ] , l o w [ v ] } low[u]=min\{low[u],low[v]\} low[u]=min{low[u],low[v]}

如果已经被弹掉了，说明无论如何这个点也不能与 u u u构成强连通分量，因为它不能到达 u u u

如果还在栈里，说明这个点肯定能到达 u u u，同样 u u u能到达他，他俩强联通。

接下来，就是非 ( s a n g ) (sang) (sang)常 ( x i n ) (xin) (xin)简 ( b i n g ) (bing) (bing)单 ( k u a n g ) (kuang) (kuang)的手 % \% %过程了

从节点 1 1 1开始 D F S DFS DFS，把遍历到的节点加入栈中。搜索到节点 u = 6 u=6 u=6时， D F N [ 6 ] = L O W [ 6 ] DFN[6]=LOW[6] DFN[6]=LOW[6]，找到了一个强连通分量。退栈到 u = v u=v u=v为止， { 6 } \{6\} {6}为一个强连通分量。

之后返回节点 5 5 5,发现 D F N [ 5 ] = L O W [ 5 ] DFN[5]=LOW[5] DFN[5]=LOW[5]，于是我们又找到了一个新的强联通分量 { 5 } \{5\} {5}

返回节点 3 3 3，继续搜索到节点 4 4 4，把 4 4 4加入堆栈。发现节点 4 4 4向节点 1 1 1有后向边，节点 1 1 1还在栈中，所以 L O W [ 4 ] = 1 LOW[4]=1 LOW[4]=1。节点 6 6 6已经出栈， ( 4 , 6 ) (4,6) (4,6)是横叉边，返回 3 3 3， ( 3 , 4 ) (3,4) (3,4)为树枝边，所以 L O W [ 3 ] = L O W [ 4 ] = 1 LOW[3]=LOW[4]=1 LOW[3]=LOW[4]=1。

继续回到节点 1 1 1，最后访问节点 2 2 2。访问边 ( 2 , 4 ) (2,4) (2,4)， 4 4 4还在栈中，所以 L O W [ 2 ] = D F N [ 4 ] = 5 LOW[2]=DFN[4]=5 LOW[2]=DFN[4]=5。返回 1 1 1后，发现 D F N [ 1 ] = L O W [ 1 ] DFN[1]=LOW[1] DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量 { 1 , 3 , 4 , 2 } \{1,3,4,2\} {1,3,4,2}。

至此， t a r j a n tarjan tarjan算法结束，我们找到了全部的 3 3 3个强联通分量 { 1 , 2 , 3 , 4 } , { 5 } , { 6 } \{1,2,3,4\},\{5\},\{6\} {1,2,3,4},{5},{6}

程序实现代码如下

inline int tarjan(int u) 
{low[u]=dfn[u]=++dfn_sum;stack[top++]=u;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(dfn(v))low[u]=min(low[u],dfn[v]);else{tarjan(v);low[u]=min(low[u],low[v]);}}if(low[u]==dfn[u]){int now=stack[--top];s_sum++;s[u]+=s_sum;while(now!=u){s[now]=s_num;now=s[--top];}}
}

所以，我们再来分析一下这道题。

首先，不难发现，如果这所有的牛都存在同一个强联通分量里。那么它们一定互相受欢迎。

那么，我们怎么来找明星呢。

很简单，找出度为 0 0 0的强联通分量中的点。这样可以保证所有的人都喜欢它，但是它不喜欢任何人，所以说不存在还有人事明星。

此题还有一个特殊情况：

如果有两个点分别满足出度为零的条件，则没有明星，这样无法满足所有的牛喜欢他。

有了上边的解释，题目就不是那么难了，代码如下

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int maxn=1e4+5;
const int maxm=5e4+5;
int to[maxm],nex[maxm],fir[maxn];
int col,num,dfn[maxn],low[maxn],de[maxn],si[maxn];
int tot=0,co[maxn],n,m;
int top,st[maxn];
template<class T> inline void read(T &x)
{x=0;register char c=getchar();register bool f=0;while (!isdigit(c)) f ^=c=='-',c=getchar();while (isdigit(c)) x=x*10+c-'0',c=getchar();if(f)x=-x;
}
template <class T> inline void print(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar('0'+x%10);
}
inline void ins(int x,int y)
{to[++tot]=y;nex[tot]=fir[x];fir[x]=tot;
}
void Tarjan(int u)
{dfn[u]=low[u]=++num;st[++top]=u;for(int i=fir[u];i;i=nex[i]){int v=to[i];if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);}else if(!co[v])low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u]){co[u]=++col;++si[col];while(st[top]!=u){++si[col];co[st[top]]=col;--top;}--top;}
}
int main()
{int x,y;read(n);read(m);for(ri i=1;i<=m;i++){read(x);read(y);ins(y,x);}for(ri i=1;i<=n;i++)if(!dfn[i])Tarjan(i);for(ri i=1;i<=n;i++)for(ri j=fir[i];j;j=nex[j])if(co[i]!=co[to[j]])de[co[to[j]]]++;int ans=0,u=0;for(ri i=1;i<=col;i++)if(!de[i])ans=si[i],u++;if(u==1)print(ans);else print(0);return 0;
}