猫史档案馆

放出例题 

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 AA 喜欢 BB，BB 喜欢 CC，那么 AA 也喜欢 CC。牛栏里共有 NN 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

 

输入格式

第一行：两个用空格分开的整数：NN 和 MM。

接下来 MM 行：每行两个用空格分开的整数：AA 和 BB，表示 AA 喜欢 BB。

 

输出格式

一行单独一个整数，表示明星奶牛的数量。

 

输入输出样例 

输入 #1

3 3
1 2
2 1
2 3

输出 #1

1

说明/提示

只有 33 号奶牛可以做明星。

【数据范围】

对于 10\%10% 的数据，N\le20N≤20，M\le50M≤50。

对于 30\%30% 的数据，N\le10^3N≤103，M\le2\times 10^4M≤2×104。

对于 70\%70% 的数据，N\le5\times 10^3N≤5×103，M\le5\times 10^4M≤5×104。

对于 100\%100% 的数据，1\le N\le10^41≤N≤104，1\le M\le5\times 10^41≤M≤5×104。

 

详细解析

 

标签：tarjan求强联通分量

 

何为强联通分量

 

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

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

 

 

如何求强联通分量

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

1.dfn，表示这个点在dfsdfs时是第几个被搜到的。

2.low，表示这个点以及其子孙节点连的所有点中dfndfn最小的值

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

4.vis，表示一个点是否在stack数组中。

我们使用tarjan的方法 (1)、首先初始化dfn[u]=low[u]=第几个被dfs到

(2)、将u存入stack[ ]中，并将vis[u]设为true

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

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

至此，tarjan完美结束

那么如果dfn[u]=low[u]这说明了什么呢？

再结合一下dfn和low的定义来看看吧

dfn表示u点被dfs到的时间，low表示u和u所有的子树所能到达的点中dfn最小的。

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

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

Q:Q: dfn可以理解，但为什么low也要这么做呢？

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

Q:Q: stack[]有什么用？

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

Q:Q: low[ ]有什么用？

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

如果遍历到的这个点已经被遍历到了，那么看它当前有没有在stack[ ]里,如果有那么low[u]=min{low[u],low[v]}

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

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

 

接下来，就是非常简单的手%过程了（雾

 

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

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

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

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

至此，tarjan算法结束，我们找到了全部的33个强联通分量{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的强联通分量中的点。这样可以保证所有的人都喜欢它，但是它不喜欢任何人，所以说不存在还有人事明星。

此题还有一个特殊情况：

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

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

 

代码如下

#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;
}

注释就不打了，往前面查。

 

爵士精品，直击OI ！

<button class="copy-btn lfe-form-sz-middle" type="button" data-v-370e72e2="" data-v-52f2d52f="">复制</button>