時間限制:10000ms 單點時限:1000ms 內存限制:256MB

描述

Recently Little Hi joined an algorithm learning group. The group consists of one algorithm master and?Nmembers. The members are numbered from 1 to?N. Each member has one or more other members as his mentors. Some members' mentor is the master himself.

Every week each member sends a report of his own learning progress and the reports collected from his pupils (if there is any) to his mentors. The group is so well designed that there is no loop in the reporting chain so no one receives his own report from his pupil. And finally the master gets every one's report (maybe more than once).

Little Hi notices that for some members their reporting routes to the master can be easily cut off by a single member's (other than the master and himself) absence from the reporting duty. They are called unstable members while the others are stable members. Given the reporting network of the group, can you find out how many members are stable?

Assume there are 4 members in the group. Member 1 and 2 both have the master as their only mentor. Member 3 has 2 mentors: member 1 and member 2. Member 4 has 1 mentor: member 3. Then member 4 is the only unstable member in the group because if member 3 is absent his learning report will be unable to be sent to the master.?

輸入

The first line contains an integer?N, the number of members.

The?i-th line of the following?N?lines describe the mentors of the?i-th member. The first integer is?Ki, the number of mentors of the?i-th member. Then follows?Ki?integers?A1?...?AN, which are his mentors' numbers. Number 0 indicates that the master is one of his mentor.

For 40% of the data, 1 ≤?N?≤ 1000.

For 100% of the data, 1 ≤?N?≤ 100000.

For 100% of the data, 1 ≤?Ki?≤ 10,?Ki?< N, 0 ≤?Ai?≤?N.?

輸出

Output the number of stable members.

樣例輸入

5 1 0 1 0 2 1 2 1 3 2 4 3

樣例輸出

3

這道題的難點在于如何找到從起點到其他節點的必經節點。然后想了好久，看了別人的討論還是沒太明白，百度到了一個題解，原來是有一個新的數據結構隱藏在這個里面——支配樹。

先來談談什么叫支配樹：什么是支配樹？支配樹是什么？XD?
對于一張有向圖（可以有環）我們規定一個起點r（為什么是r呢？因為網上都是這么規定的），從r點到圖上另一個點w可能存在很多條路徑（下面將r到w簡寫為r->w）。?
如果對于r->w的任意一條路徑中都存在一個點p，那么我們稱點p為w的支配點（當然這也是r->w的必經點），注意r點不討論支配點。下面用idom[u]表示離點u最近的支配點。?
對于原圖上除r外每一個點u，從idom[u]向u建一條邊，最后我們可以得到一個以r為根的樹。這個樹我們就叫它“支配樹”。

簡化問題：

樹：對于一顆樹，我們用r表示其根節點，那么從r->u上的點都是u的支配點，idom[u]就是u的父親節點，這個很容易實現。

有向無環圖：因為是有向無環圖，所以我們可以用拓撲序列構建樹。假設第x個節點是u，那么1-x-1的節點都已經處理好了，我們只需要把u節點的所有直接前驅的最近公共祖先找到即可。

解題思路：

·數據存儲：
? ? 根據輸入的成員信息，可以構建一個有向圖來直觀地表示成員之間的信息。此時Master和每一個成員分別用一個點來表示，當成員A是成員B的mentor時，點A到點B，之間就存在一條邊。題目中給出的樣例可以用下圖來表示：

? ? ??這里用編號0來表示Master。此時，“不穩定成員”的定義就是：如果存在某一個編號不為0的點，使得從點0到該點的所有路徑中都必須經過這個點，那么該點代表的成員就是“不穩定成員”。上圖中，從點0到點4的所有路徑必經過點3，因此成員4是不穩定成員。

支配樹：
? ? 將上面“不穩定成員”的定義加以拓展，去掉“非0點”的限制，可以得到“支配點”的定義，即：對于某一個目標點，如果存在一個點，使得圖中從起點到目標點所有路徑都必須經過該點，那么該點就是目標點的“支配點”。上圖中：點1、2、3、4的支配點分別為：0、0、0、0和3。顯然，如果從起點出發可以到達圖中的所有點，那么起點就是圖中所有點的“支配點”。
? ? 一個點的“支配點”不一定只有一個。例如：如果對于某個點，從起點到該點的路徑只有1條，那么該路徑上的所有點都是該點的支配點。對于有多個支配點的情況，我們可以找到一個支配點，它距離目標點的最近，這個點我們成為“直接支配點”。對于給定的圖，一個點可能用有多個支配點，但它的直接支配點一定是唯一的。此時，出去起點外，所有的點都有自己唯一的“直接支配點”。
? ? 而“支配樹”是這樣的一種多叉樹：圖中的點對應于樹的節點，而每一個節點的父節點則是它的直接支配點。上文中的圖構成的支配樹如下： ? ? ? 顯然，完成樹的構建后，每個點的父節點就是它的直接支配點，而這個點的所有祖先節點都是它的支配點。此時，根據題意，我們要找的“穩定成員”就是直接支配點是0號點（Master）的成員，也就是支配樹中根節點的孩子。?

·建樹：
? ? 為了建立支配樹，就必須知道每個點的直接支配點。考慮原圖中每個點的“前驅點”，本題中即考慮每個成員的mentor。如果某個成員只有一個mentor，那么顯然從Master到該成員的路徑一定都會經過他的mentor，因此mentor就是該成員的直接支配點；對于抽象的圖而言，如果某一個點只有一個前驅點，那么該前驅點就是當前點的直接支配點；如果某個成員有多個mentor，那么對于某一個mentor而言，從Master到該成員就未必會經過它，所以，當某個成員擁有多個mentor時，他的mentor都不是他的直接支配點；對于抽象的圖而言，如果一個點有多個前驅，那么這些前驅點都不是它的直接支配點，我們需要考慮這些前驅節點的支配點，當這些前驅節點擁有共同的一個支配點時，說明從起點到這些前驅點的所有路徑必會經過這個共有的支配點，也就是說，從起點到目標點的所有路徑都會經過這個共有的支配點，因此這個共有的支配點就是目標點的直接支配點。這個結論對于只有一個前驅節點的情況也使用
? ? 根據支配樹的定義，多個節點共有的支配點是明確的，就是他們的公共祖先，而我們要找的則是最近公共祖先。這個結論對于只有一個前驅節點的情況也使用，因為如果只有一個點，那么它的最近公共祖先就是它自己。
? ? 于是，建立支配樹的過程就是：首先將起點加入到樹中，作為整個支配樹的根，然后對于每一個節點，找到其所有前驅節點在支配樹中的最近公共祖先，這個祖先節點就是當前節點的父節點。

·拓撲排序：
? ? 上面的建樹過程有一個條件必須要保證，即某個點要加入到樹中時，必須確保它的所有前驅點已經在樹中，這樣才可以找到這些點的最近公共祖先。因此，節點添加入樹中的順序是很重要的。我們可以通過拓撲排序找到合適的順序，拓撲排序的結果就是節點加入樹的順序。這樣就保證了前驅節點一定先于當前節點加入到樹中。

·最近公共祖先：
? ? 建樹的過程設計到了求多個節點的最近公共祖先。我們可以采用一種復雜度為O(lgn)的算法來求解它?？紤]每個節點在樹中的高度，將高度小的節點沿著父節點指針向上移動，在所有節點的高度相同時再同時沿著父節點指針向上移動，當所有的節點都到達同一個節點時，這個終點就是這些節點的最近公共祖先。

? ? 以上是本題的解答思路，完成建立支配樹后，統計一下根節點有多少個孩子，就是本題的答案。

#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> using namespace std;const int maxn = 100005; struct Edge {int to,next; }edge[maxn*10]; int n,cnt,ans,head[maxn],deg[maxn]; int dep[maxn],parent[maxn],tmp[15]; //tmp[i]表示第i個直接前驅回溯到的節點 vector<int> g[maxn];void addedge(int u,int v) {edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt++; }int LCA(int u) {int min_dep = -1;for(int i = 0; i < g[u].size(); i++){int v = g[u][i];tmp[i] = v;if(min_dep == -1 || min_dep > dep[v])min_dep = dep[v];}for(int i = 0; i < g[u].size(); i++){while(dep[tmp[i]] > min_dep)tmp[i] = parent[tmp[i]];}while(true){int i;for(i = 1; i < g[u].size(); i++)if(tmp[i] != tmp[0])break;if(i >= g[u].size()) break;for(int i = 0; i < g[u].size(); i++)tmp[i] = parent[tmp[i]];}return tmp[0]; }void bfs() {queue<int> q;for(int i = 0; i <= n; i++)if(deg[i] == 0)q.push(i);while(!q.empty()){int u = q.front();q.pop();for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;deg[v]--;if(deg[v] == 0){parent[v] = LCA(v);dep[v] = dep[parent[v]] + 1;if(parent[v] == 0) ans++;q.push(v);}}} }int main() {while(scanf("%d",&n)!=EOF){memset(head,-1,sizeof(head));memset(deg,0,sizeof(deg));for(int i = 0; i <= n; i++) g[i].clear();for(int i = 1; i <= n; i++){int k;scanf("%d",&k);for(int j = 1; j <= k; j++){int u;scanf("%d",&u);addedge(u,i);g[i].push_back(u);deg[i]++;}}ans = 0;bfs();printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hihocoder #1343 : Stable Members(支配树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。