P2341 [HAOI2006]受歡迎的牛--很細--Sabrina--Sabrinadol

題目背景

本題測試資料已修複。

題目描述

每頭奶牛都夢想成為牛棚裡的明星。被所有奶牛喜歡的奶牛就是一頭明星奶牛。所有奶

牛都是自戀狂，每頭奶牛總是喜歡自己的。奶牛之間的“喜歡”是可以傳遞的——如果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

題解

對于本題各位大佬的願望肯定是AC，是以我們直接講滿分算法

1.題目分析

本題的意思大概就是我們選出的明星牛每頭牛都喜歡，将牛看做一個點，牛與牛之間的喜歡看做一條路

，那麼我們是不是就相當于在一個有向圖中去找強連通子圖了對吧

2.主要算法分析

（1）因為同一頭牛被所有牛喜歡，那麼它不能喜歡任意除了自己這個聯通子圖的牛的其他牛，是以在每個聯通子圖下統計是否出度為0，就好了。同樣，如果存在兩個或兩個以上的出度為0的點（已經縮點之後），那麼直接輸出0就好了。

（2）那麼既然要找強連通子圖，就必須要用到Tarjan算法

我摘抄一段Tarjan算法的講解（懶。。）

Tarjan算法介紹：

Tarjan算法是圖論中的一種算法，用作于圖的聯通性

它可以做什麼？

根據 Robert Tarjan 的名字命名的算法Tarjan算法可以線上性時間内求出無向圖的割點與橋，再進一步的求出雙聯通分量，也在資料結構上做出了貢獻。

Tarjan算法的用途

1.求橋和割點

2.求點和邊的雙連通分量

3.求強連通*

做法基礎

Tarjan算法基于圖的深度優先周遊上（沒錯！就是與深度優先搜尋（DFS）一樣的東西）

（如果沒學過這樣東西的人可以先收藏一下，等學過了在看）

Targan算法的流程

利用dfs來周遊圖來建構一種數型的結構

Tarjan算法的兩個核心數組

dfn：我們用dfn數組記錄

low：我們用low[i]表示一個節點的子樹中可以到達最小的dfn

（顯然對于一個剛剛周遊到的點我們給他賦上一個新的dfn，low）

摘自：huangdanning-HDN

3.tarjan算法完美結束之後

我們需要進行判斷該點及其子孫是否能夠夠成一個強連通子圖，這裡隻需要判斷一下

dfn[u]==low[u]就好了

4.對于2 ，3給出片段代碼

代碼注釋很詳細

void tarjan(int u)
{
	num++;
	dfn[u]=num;//時間戳 
	low[u]=num;//初始化這個low 
	st[++top]=u;//入棧 
	for(int i=first[u];i;i=next[i])//鄰接表周遊 
	{
		int v=to[i];//存儲到達的點 
		if(!dfn[v])//如果該點還沒有被掃過，時間戳為0 
		{
			tarjan(v);//那就向下掃友善找low 
			low[u]=min(low[u],low[v]);//low取最小值，看看能不能成環 
		}
		else if(!co[v])//判斷是否在棧中 
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u])//如果相等就記錄，出棧
	{
		co[u]=++col;//co存強連通分量元素 ，其值代表在第幾個強連通子圖中
		++si[col];//代表每個強聯通子圖中對應的元素個數
		while(st[top]!=u)
		{
			++si[col];
			co[st[top]]=col;
			--top;
		}
		--top;//将st【top】（==u）出棧
	}
}
           

5.因為題目中給出的資料極大如果用鄰接矩陣勢必要超出空間，是以我們需要使用

鄰接表

來存圖，如下，有興趣的可以試一試前向星

大緻内容就是開三個數組一個存點，另外兩個存邊，代碼中有解釋

void getsin(int a,int b)
{
	total++;
	to[total]=b;//to來存儲點
	next[total]=first[a];//next表示接下來的邊
	first[a]=total;//first表示該點連的第一條邊
}

           

cin>>n>>m;
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		getsin(y,x);//将出度巧妙轉化為入度
	}
           

附上AC代碼

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define maxn 100005
using namespace std;
int n,m;
int to[maxn];
int num;
int st[maxn];
int stack[maxn];
int top;
int col,dfn[maxn],low[maxn],de[maxn],si[maxn];
int co[maxn];
int next[maxn],first[maxn];
int total;
void getsin(int a,int b)
{
	total++;
	to[total]=b;
	next[total]=first[a];
	first[a]=total;
}
void tarjan(int u)
{
	num++;
	dfn[u]=num;
	low[u]=num;
	st[++top]=u;
	for(int i=first[u];i;i=next[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()
{
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		getsin(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])	
		tarjan(i);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=first[i];j;j=next[j])
		{
			if(co[i]!=co[to[j]])//在不同的強連通圖中
			de[co[to[j]]]++;//求入度
		}
	}
	int ans=0;
	int u=0;
	for(int i=1;i<=col;i++)
	{
		if(!de[i])//如果入度為零說明為明星牛
		{
			ans=si[i];//si【i】代表的圖中一共有多少頭牛
			u++;
		}
	}
	if(u==1)
	cout<<ans;
	else
	cout<<"0";//如果超過2個或等于0都是沒有明星牛的
	while(1)
	cout<<"Sabrina"<<endl//防抄
	return 0;
}