【luogu2835】 刻錄CD光牒

(​​http://www.elijahqi.win/2017/07/03/%E3%80%90luogu2835%E3%80%91-%E5%88%BB%E5%BD%95%E5%85%89%E7%9B%98/%20%E2%80%8E​​​)

題目描述

在JSOI2005夏令營快要結束的時候，很多營員提出來要把整個夏令營期間的資料刻錄成一張CD光牒給大家，以便大家回去後繼續學習。組委會覺得這個主意不錯！可是組委會一時沒有足夠的空CD光牒，沒法保證每個人都能拿到刻錄上資料的CD光牒，又來不及去買了，怎麼辦呢？！

組委會把這個難題交給了LHC，LHC分析了一下所有營員的地域關系，發現有些營員是一個城市的，其實他們隻需要一張就可以了，因為一個人拿到CD光牒後，其他人可以帶着U盤之類的東西去拷貝啊！

可是，LHC調查後發現，由于種種原因，有些營員并不是那麼的合作，他們願意某一些人到他那兒拷貝資料，當然也可能不願意讓另外一些人到他那兒拷貝資料，這與我們JSOI宣揚的團隊合作精神格格不入！！！

現在假設總共有N個營員（2<=N<=200），每個營員的編号為1~N。LHC給每個人發了一張調查表，讓每個營員填上自己願意讓哪些人到他那兒拷貝資料。當然，如果A願意把資料拷貝給B，而B又願意把資料拷貝給C，則一旦A獲得了資料，則B，C都會獲得資料。

現在，請你編寫一個程式，根據回收上來的調查表，幫助LHC計算出組委會至少要刻錄多少張CD光牒，才能保證所有營員回去後都能得到夏令營資料？

輸入輸出格式

輸入格式：

先是一個數N，接下來的N行，分别表示各個營員願意把自己獲得的資料拷貝給其他哪些營員。即輸入資料的第i+1行表示第i個營員願意把資料拷貝給那些營員的編号，以一個0結束。如果一個營員不願意拷貝資料給任何人，則相應的行隻有1個0，一行中的若幹數之間用一個空格隔開。

輸出格式：

一個正整數，表示最少要刻錄的CD光牒數。

#include<cstdio>
#include<cstring>
#define N 88000
#define N1 220
struct node{
    int x,y,next;
}data[N];
int num,top,stack[N1],low[N1],dfn[N1],h[N1],s,b[N1],n,a1[N1],a2[N1];
bool stackf[N1];
inline void insert1(int x,int y){
    data[++num].x=x;data[num].y=y;data[num].next=h[x];h[x]=num;
}
void tarjan(int u){
    dfn[u]=++num;low[u]=num;
    stack[++top]=u;stackf[u]=true;
    for (int i=h[u];i;i=data[i].next) {
        int v=data[i].y;
        if (dfn[v]==0){
            tarjan(v);
            if (low[v]<low[u]) low[u]=low[v];
        } else{
            if (stackf[v]&&dfn[v]<low[u]) low[u]=dfn[v];
        }
    } 
    if(dfn[u]==low[u]){
        ++s;int y;
        do{
            y=stack[top--];b[y]=s;
            stackf[y]=false;
        }while(y!=u);
    } 
}
int main(){
    //freopen("2835.in","r",stdin);
    //freopen("2835.out","w",stdout);
    scanf("%d",&n);
    memset(h,0,sizeof(h));num=0;
    for (int i=1;i<=n;++i){
        int tmp;
        scanf("%d",&tmp);
        while (tmp!=0){
            insert1(i,tmp);
            scanf("%d",&tmp);
        }
    }
    int num1=num;num=0;
    memset(low,0,sizeof(low));
    memset(stackf,false,sizeof(stackf));
    for (int i=1;i<=n;++i){
        if (dfn[i]==0) tarjan(i);
    }
    //for (int i=1;i<=n;++i) printf("%d\n",b[i]);
    for (int i=1;i<=num1;++i){
        int x=data[i].x,y=data[i].y;
        if (b[x]!=b[y]){
            a1[b[x]]++;a2[b[y]]++;
        }
    }
    int ans=0;
    for (int i=1;i<=s;++i){
        if (a2[i]==0) ans++;
    }
    printf("%d",ans);
    return 0;
}