[POI2005]SKA-Piggy Banks tarjan 水题

忘是亡心i 2021-11-17 16:26 209阅读 0赞

## Description ##

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

## Input ##

第一行一个整数 N (1 <= N <= 1.000.000) – 表示存钱罐的总数. 接下来每行一个整数,第 i+1行的整数代表第i个存钱罐的钥匙放置的存钱罐编号.

## Output ##

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

正解是并查集，专门卡 $tarjan$ 的空间

#include<bits/stdc++.h>
    #define maxn 1000002 
    using namespace std;
    void setIO(string s)
    {
    	string in=s+".in"; 
    	freopen(in.c_str(),"r",stdin); 
    }                           
    stack<int>S; 
    int scc,cnt,edges; 
    int low[maxn],pre[maxn],vis[maxn],bin[maxn],du[maxn];  
    vector<int>G[maxn];         
    void tarjan(int u)
    {
    	S.push(u); 
    	low[u]=pre[u]=++scc; 
    	vis[u]=1; 
    	for(int i=0,sz=G[u].size();i<sz;++i)
    	{
    		int v=G[u][i];          
    		if(!vis[v]) tarjan(v), low[u]=min(low[u],low[v]); 
    		else if(vis[v]==1) low[u]=min(low[u], pre[v]); 
    	}
    	if(low[u]==pre[u])
    	{
    		++cnt; 
    		for(;;)
    		{
    			int x=S.top(); S.pop(); 
    			bin[x]=cnt, vis[x]=-1; 
    			if(x==u) break; 
    		}
    	}
    }
    int main()
    {
    	// setIO("input"); 
    	int n; 
    	scanf("%d",&n); 
    	for(int i=1;i<=n;++i)
    	{
    		int a; 
    		scanf("%d",&a); 
    		G[a].push_back(i); 
    	}
    	for(int i=1;i<=n;++i) 
    		if(!vis[i]) 
    			tarjan(i);
    	for(int i=1;i<=n;++i) 
    	{
    		for(int j=0,sz=G[i].size();j<sz;++j) 
    		{
    			if(bin[i]!=bin[G[i][j]]) ++du[bin[G[i][j]]];                            
    		}
    	}
    	int ans=0;   
    	for(int i=1;i<=cnt;++i) if(!du[i]) ++ans; 
    	printf("%d\n",ans);   
    	return 0; 
    }

转载于:https://www.cnblogs.com/guangheli/p/11037726.html