[Poi2005]Piggy Banks小猪存钱罐

题目描述

Byteazar有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.

输入格式

第一行一个整数 N (1 <= N <= 1.000.000)表示存钱罐的总数.

接下来每行一个整数,第 i+1行的整数代表第i个存钱罐的钥匙放置的存钱罐编号.

输出格式

一个整数表示最少打破多少个存钱罐.

分析题目性质。

题目给了若干个单向关系，我们可以依照这个建出一张有向图。那么显然，只要我们有了一个存钱罐的钥匙，那这个强连通分量里的所有存钱罐都可以打开了。那么我们对图中所有强连通分量进行缩点，入度>0的点就通过其它点得到钥匙，入度为0的点我们就砸开它。所以答案就是入度为0的强连通分量个数。

强连通分量用Tarjan来求，时间复杂度为O(N)

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#define maxn 1000001

using namespace std;

vector<int> to[maxn];

int dfn[maxn],low[maxn],tot;

int col[maxn],ind[maxn],cnt;

int stack[maxn],top;

bool instack[maxn];

int n,ans;

inline int read(){

    register int x(0),f(1); register char c(getchar());

    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }

    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

    return x*f;

}

void tarjan(int u){

    dfn[u]=low[u]=++tot,stack[++top]=u,instack[u]=true;

    for(register int i=0;i<to[u].size();i++){

        int v=to[u][i];

        if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);

        else if(instack[v]) low[u]=min(low[u],dfn[v]);

    }

    if(low[u]==dfn[u]){

        int v; cnt++;

        do{ v=stack[top--],instack[v]=false; col[v]=cnt; }while(v!=u);

    }

}

int main(){

    n=read();

    for(register int i=1;i<=n;i++) to[read()].push_back(i);

    for(register int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);

    for(register int i=1;i<=n;i++){

        for(register int j=0;j<to[i].size();j++){

            int v=to[i][j];

            if(col[i]!=col[v]) ind[col[v]]++;

        }

    }

    for(register int i=1;i<=cnt;i++) if(!ind[i]) ans++;

    printf("%d\n",ans);

    return 0;

}

巴特西

[Poi2005]Piggy Banks小猪存钱罐

题目描述

输入格式

第一行一个整数 N (1 <= N <= 1.000.000)表示存钱罐的总数.

接下来每行一个整数,第 i+1行的整数代表第i个存钱罐的钥匙放置的存钱罐编号.

输出格式

一个整数表示最少打破多少个存钱罐.

分析题目性质。

强连通分量用Tarjan来求，时间复杂度为O(N)

最新文章

热门文章