洛谷 P3420 [POI2005]SKA-Piggy Banks

题目描述

Byteazar the Dragon has

TaskWrite a programme which:

reads from the standard input the number of piggy banks and the deployment of their corresponding keys,finds the minimal number of piggy banks to be smashed in order to gain access to all of them,writes the outcome to the standard output.

Byteazar the Dragon拥有N个小猪存钱罐。每一个存钱罐能够用相应的钥匙打开或者被砸开。Byteazar已经将钥匙放入到一些存钱罐中。现在已知每个钥匙所在的存钱罐，Byteazar想要买一辆小汽车，而且需要打开所有的存钱罐。然而，他想要破坏尽量少的存钱罐，帮助Byteazar去决策最少要破坏多少存钱罐。

任务：

写一段程序包括：

读入存钱罐的数量以及相应的钥匙的位置，求出能打开所有存钱罐的情况下，需要破坏的存钱罐的最少数量并将其输出。

输入输出格式

输入格式：

The first line of the standard input contains a single integer

第一行：包括一个整数N（1<=N<=1000000)，这是Byteazar the Dragon拥有的存钱罐的数量。

存钱罐（包括它们对应的钥匙）从1到N编号。

接下来有N行：第i+1行包括一个整数x，表示第i个存钱罐对应的钥匙放置在了第x个存钱罐中。

输出格式：

The first and only line of the standard output should contain a single integer - the minimal number of piggy banks to be smashed in order to gain access to all of the piggy banks.

仅一行：包括一个整数，表示能打开所有存钱罐的情况下，需要破坏的存钱罐的最少数量。

输入输出样例

输入样例#1：复制

输出样例#1：复制

2
思路：建图+tarjin缩点。最后入度为0的点的个数就是所要求的答案。

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 1000010
using namespace std;
map<int,int>ma[MAXN];
int col[MAXN];
int n,tot,tim,ans,top,sumcol;
int vis[MAXN],dfn[MAXN],low[MAXN];
int to[MAXN],net[MAXN],head[MAXN];
int stack[MAXN],visstack[MAXN],into[MAXN];
void add(int u,int v){
    to[++tot]=v;net[tot]=head[u];head[u]=tot;
}
void tarjin(int now){
    low[now]=dfn[now]=++tim;
    stack[++top]=now;
    vis[now]=1;
    visstack[now]=1;
    for(int i=head[now];i;i=net[i])
        if(visstack[to[i]])
            low[now]=min(low[now],dfn[to[i]]);
        else if(!vis[to[i]]){
            tarjin(to[i]);
            low[now]=min(low[now],low[to[i]]);
        }
    if(low[now]==dfn[now]){
        sumcol++;
        col[now]=sumcol;
        while(stack[top]!=now){
            col[stack[top]]=sumcol;
            visstack[stack[top]]=0;
            top--;
        }
        visstack[now]=0;
        top--;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        add(x,i);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])    tarjin(i);
    for(int i=1;i<=n;i++)
        for(int j=head[i];j;j=net[j])
            if(col[i]!=col[to[j]])
                if(ma[col[i]].find(col[to[j]])==ma[col[i]].end()){
                    ma[col[i]][col[to[j]]]=1;
                    into[col[to[j]]]++;
                }
    for(int i=1;i<=sumcol;i++)
        if(into[i]==0)    ans++;
    cout<<ans;
}

这个题也可以用并查集做。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 1000001
using namespace std;
int n,ans;
int fa[MAXN];
int find(int x){
    if(fa[x]==x)    return x;
    return fa[x]=find(fa[x]);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)    fa[i]=i;
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        int dx=find(x);
        int dy=find(i);
        fa[dy]=dx;
    }
    for(int i=1;i<=n;i++)
        if(fa[i]==i)    ans++;
    cout<<ans;
}

细雨斜风作晓寒。淡烟疏柳媚晴滩。入淮清洛渐漫漫。雪沫乳花浮午盏，蓼茸蒿笋试春盘。人间有味是清欢。