Loading...

洛谷P2661 信息传递

check评论:0 条 remove_red_eye浏览量:358 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-12

$tarjan$ 裸题

因为这是一个$n$点$n$边,并且每个点出度均为$1$的图,很容易可以知道,在一个环内不会存在另外一个小环,则我们只需$tarjan$后,如果当前环大小大于$1$,$ans$和其取一个$min$即可

#include <bits/stdc++.h>
using namespace std;
int head[200010],dfn[200010],low[200010],cnt,n,flag,belong[200010],na,ans=0x3f3f3f3f;
struct edge
{
    int next,to;
}e[200010];
stack<int> st;
void add(int u,int v)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++cnt;
    st.push(u);
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!belong[v])
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    int siz=0;
    if(dfn[u]==low[u])
    {
        na++;
        while(1)
        {
            int x=st.top();
            st.pop();
            siz++;
            belong[x]=na;
            if(x==u)
            {
                break;
            }
        }
        if(siz>1)
        {
            ans=min(ans,siz);
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        add(i,x);
    }
    cnt=0; 
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名