HAOI2006 （洛谷P2341)受歡迎的牛 題解

題目描述

友情鏈接原題

每頭奶牛都?jí)粝氤蔀榕Ｅ锢锏拿餍恰１凰心膛Ｏ矚g的奶牛就是一頭明星奶牛。所有奶

牛都是自戀狂，每頭奶牛總是喜歡自己的。奶牛之間的“喜歡”是可以傳遞的——如果A喜

歡B，B喜歡C，那么A也喜歡C。牛欄里共有N 頭奶牛，給定一些奶牛之間的愛(ài)慕關(guān)系，請(qǐng)你

算出有多少頭奶牛可以當(dāng)明星。

輸入輸出格式

輸入格式：

第一行：兩個(gè)用空格分開(kāi)的整數(shù)：N和M

第二行到第M + 1行：每行兩個(gè)用空格分開(kāi)的整數(shù)：A和B，表示A喜歡B

輸出格式：

第一行：?jiǎn)为?dú)一個(gè)整數(shù)，表示明星奶牛的數(shù)量

輸入輸出樣例

輸入樣例#1：

3 3
1 2
2 1
2 3

輸出樣例#1：

1

說(shuō)明

只有 3 號(hào)奶牛可以做明星

【數(shù)據(jù)范圍】

10%的數(shù)據(jù)N<=20, M<=50

30%的數(shù)據(jù)N<=1000,M<=20000

70%的數(shù)據(jù)N<=5000,M<=50000

100%的數(shù)據(jù)N<=10000,M<=50000

題目分析

這是一道強(qiáng)連通分量的題

首先把樣例拿來(lái)畫(huà)一下（解決圖論題目常規(guī)操作），得到如下的圖：

我們可以發(fā)現(xiàn)一號(hào)和二號(hào)可以構(gòu)成一個(gè)強(qiáng)連通分量，然后就會(huì)想到tarjan縮點(diǎn)。。把一號(hào)和二號(hào)縮點(diǎn)后，可以得到如下的圖：

我們推論：縮點(diǎn)后出度為零的點(diǎn)為明星牛（假如出度為零的點(diǎn)是一個(gè)強(qiáng)連通分量的縮點(diǎn)，那么這個(gè)強(qiáng)連通分量中的所有牛都是明星牛）這個(gè)其實(shí)很好證，假如明星牛的出度不為0，它就會(huì)和其他點(diǎn)構(gòu)成一個(gè)強(qiáng)連通分量，那么就是縮點(diǎn)不徹底，而我們討論的是完全縮點(diǎn)后的情況。

我們?cè)谂e一個(gè)例子

縮點(diǎn)后的圖是這樣的

這兩個(gè)點(diǎn)都是出度為0，但是我們發(fā)現(xiàn)并沒(méi)有明星牛。原因是有兩個(gè)點(diǎn)出度為零。所以推論應(yīng)該改為：縮點(diǎn)后唯一的出度為0的點(diǎn)是明星牛，這樣也可以避免掉單獨(dú)的點(diǎn)帶來(lái)的影響。

假如這整個(gè)圖就是一個(gè)強(qiáng)連通圖，那么每一頭牛都是明星牛（縮點(diǎn)后只有一個(gè)點(diǎn)，仍然滿足推論）。

然后這個(gè)題就簡(jiǎn)單了，算是裸的tarjan。

附上標(biāo)程

#include<bits/stdc++.h>
#define maxn 1000000
using namespace std;
int Next[maxn],a=0,F[maxn],Head[maxn];
int cmpi[maxn],out[maxn],E[maxn],cmp[maxn],s[maxn];
int dfn[maxn],low[maxn],top=0,cmpid=0,tim=0;
bool V[maxn],D[maxn];
void ins(int x,int y,int i)
{
    E[i]=y;
    Next[i]=Head[x];
    Head[x]=i;
}//鏈?zhǔn)角跋蛐?int find()
{
    int ans=0;
    for(int i=1;i<=a;i++)
    {
        for(int p=Head[F[i]];p;p=Next[p])//列舉這個(gè)點(diǎn)的所有鄰接點(diǎn)
        {
            if(!D[E[p]])ans++;//如果這個(gè)點(diǎn)的鄰接點(diǎn)不和他在一個(gè)強(qiáng)聯(lián)通分量的話，那么我們就發(fā)現(xiàn)他所在的分量有了出度
        }
    }
    return ans;
}//找一組強(qiáng)連通分量的出度
void tarjan(int u)
{
    dfn[u]=low[u]=++tim;
    s[++top]=u;
    V[u]=true;
    for(int p=Head[u];p;p=Next[p])
    {
        int y=E[p];
        if(!dfn[y])
        {
            tarjan(y);
            low[u]=min(low[y],low[u]);
        }
        else
        {
            if(V[y])low[u]=min(low[u],dfn[y]);
        }
    }
    if(dfn[u]==low[u])
    {
        int y;
        cmpid++;
        do
        {
            y=s[top--];
            V[y]=false;
            F[++a]=y;//將這個(gè)點(diǎn)存入暫時(shí)數(shù)組
            D[y]=true;
            cmpi[cmpid]++;
        }while(y!=u);
        cmp[cmpid]=find();//cmp存儲(chǔ)他的出度
        a=0;
        memset(D,false,sizeof(D));//D數(shù)組表示這個(gè)點(diǎn)在不在這個(gè)強(qiáng)連通分量
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        ins(a,b,i);
    }
    for(int i=1;i<=n;i++)
       if(!dfn[i])tarjan(i);
    int c=0,ans;
    for(int i=1;i<=cmpid;i++)
      if(!cmp[i])c++,ans=i;//檢查圖是否連通
    if(c==1)printf("%d",cmpi[ans]);//輸出
    else printf("0");
    return 0;
}