tarjan通俗易懂题

た入场券 2021-10-18 12:42 464阅读 0赞

洛谷2661

[https://www.luogu.org/problemnew/show/P2661][https_www.luogu.org_problemnew_show_P2661]

分析：求缩点后成环中，环大小最小的size

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int M=2e5+5;
    vector<int>e[M];
    int vis[M],dfn[M],low[M],cnt,ans=M;
    stack<int>S;
    void tarjan(int u){
        dfn[u]=low[u]=++cnt;
        vis[u]=1;
        S.push(u);
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i];
            if(!dfn[v]){
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }
            else if(vis[v])
                low[u]=min(low[u],dfn[v]);
        }
        if(low[u]==dfn[u]){
            int countt=0;
            while(true){
                int t=S.top();
                S.pop();
                vis[t]=0;
                countt++;
                if(t==u)
                    break;
            }
            if(countt>1)
                ans=min(ans,countt);
        }
    }
    int main(){
    
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            e[i].push_back(x);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i])
                tarjan(i);
        }
        cout<<ans;
        return 0;
    }

[https://www.luogu.org/problemnew/show/P1726][https_www.luogu.org_problemnew_show_P1726]

分析：还是求环的大小，不过要在存路径时加些操作

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<stack>
    #include<vector>
    using namespace std;
    const int M=5e4+4;
    int dfn[M],low[M],vis[M],a[M],b[M],cnt;
    vector<int>e[M];
    stack<int>S;
    int ans;
    void tarjan(int u){
        dfn[u]=low[u]=++cnt;
        vis[u]=1;
        S.push(u);
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i];
            if(!dfn[v]){
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }
            else if(vis[v])
                low[u]=min(low[u],dfn[v]);
        }
        if(low[u]==dfn[u]){
            int countt=0;
            while(true){
                int t=S.top();
                S.pop();
                vis[t]=0;
                a[countt++]=t;
                if(t==u)
                    break;
            }
            if(ans<=countt){
                sort(a,a+countt);
                if(ans==countt){
                    int flag=0;
                    for(int i=0;i<countt;i++)
                        if(a[i]<b[i]){
                            flag=1;
                            break;
                        }
                        else if(a[i]>b[i])
                            break;
                    if(flag==1)
                        for(int i=0;i<countt;i++)
                            b[i]=a[i];
                }
                else{
                    for(int i=0;i<countt;i++)
                        b[i]=a[i];
                }
                ans=countt;
            }
        }
    }
    int main(){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int u,v,t;
            scanf("%d%d%d",&u,&v,&t);
            if(t==1)
                e[u].push_back(v);
            else
                e[u].push_back(v),e[v].push_back(u);
    
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                tarjan(i);
        printf("%d\n",ans);
        for(int i=0;i<ans;i++){
            printf("%d ",b[i]);
        }
        return 0;
    }

[https://www.luogu.org/problemnew/show/P2341][https_www.luogu.org_problemnew_show_P2341]

分析：所求量一定为经缩点后唯一出度为0的强联通分量的大小

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<stack>
    #include<vector>
    using namespace std;
    const int M=1e4+4;
    const int N=5e4+5;
    vector<int>e[M];
    
    int out[M],in[M],dfn[M],low[M],vis[M],sz[N],cnt,tot,cmp[N];
    stack<int>S;
    void tarjan(int u){
        low[u]=dfn[u]=++cnt;
        vis[u]=1;
        S.push(u);
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i];
            if(!dfn[v]){
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }
            else if(vis[v])
                low[u]=min(low[u],dfn[v]);
        }
        if(dfn[u]==low[u]){
            int countt=0;
            tot++;
            while(true){
                int t=S.top();
                S.pop();
                vis[t]=0;
                cmp[t]=tot;
                countt++;
                if(t==u)
                    break;
            }
            sz[tot]=countt;
        }
    }
    int main(){
        int n,m;
        scanf("%d%d",&n,&m);
        int u,v;
        for(int i=1;i<=m;i++){
    
            scanf("%d%d",&u,&v);
            e[u].push_back(v);
        }
    
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                tarjan(i);
        int sum=0;
        for(int i=1;i<=n;i++)
        for(int j=0;j<e[i].size();j++){
            int v=e[i][j];
            if(cmp[i]!=cmp[v])
                out[cmp[i]]++,in[cmp[v]]++;
        }
        int countt=0,sign;
        for(int i=1;i<=tot;i++)
            if(out[i]==0)
                countt++,sign=i;
        if(countt>1)
            return puts("0"),0;
        printf("%d\n",sz[sign]);
    
        return 0;
    }

转载于:https://www.cnblogs.com/starve/p/11192740.html

[https_www.luogu.org_problemnew_show_P2661]: https://www.luogu.org/problemnew/show/P2661
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211018/3834b1ec571a474985b49b38fd2a2c00.png
[https_www.luogu.org_problemnew_show_P1726]: https://www.luogu.org/problemnew/show/P1726
[https_www.luogu.org_problemnew_show_P2341]: https://www.luogu.org/problemnew/show/P2341