[POI2005]SKA-Piggy Banks (Tarjan缩点)

题目链接

Solution

\(Tarjan\) 缩点乱搞.

考虑到环内如果有一个被打开,那么也就全部打开了.

然后很显然入度为 \(0\) 的点需要被砸破.

所以缩点之后找到入度为 \(0\) 的即可.

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn=1000008;

struct sj{int to,next;}a[maxn];

int head[maxn],size;

int dfn[maxn],low[maxn];

int sta[maxn],top,belong[maxn];

int cnt,tot,v[maxn],n;

int du[maxn],ans;

void add(int x,int y)

{

    a[++size].to=y;

    a[size].next=head[x];

    head[x]=size;

}

void tarjan(int x)

{

    dfn[x]=low[x]=++tot;

    sta[++top]=x;

    v[x]=1;

    for(int i=head[x];i;i=a[i].next)

    {

        int tt=a[i].to;

        if(!dfn[tt]){

          tarjan(tt);

          low[x]=min(low[x],low[tt]);

        }

        else if(v[tt]) low[x]=min(low[x],dfn[tt]);

    }

    if(dfn[x]==low[x])

    {

      belong[x]=++cnt;

      v[x]=0;

      do{

        belong[sta[top]]=cnt;

        v[sta[top]]=0;

      }while(sta[top--]!=x);

    }

}

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(!dfn[i])tarjan(i);

    for(int x=1;x<=n;x++)

    for(int i=head[x];i;i=a[i].next)

    {

        int tt=a[i].to;

        if(belong[tt]!=belong[x])

        du[belong[tt]]++;

    }

    for(int i=1;i<=cnt;i++)

    if(!du[i])

    ans++;

    cout<<ans<<endl;

}

巴特西

[POI2005]SKA-Piggy Banks (Tarjan缩点)

题目链接

Solution

Code

最新文章

热门文章