tarjan通俗易懂题-蒲公英云

tarjan通俗易懂题

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

洛谷2661

https://www.luogu.org/problemnew/show/P2661

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

#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

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

#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

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

#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;
}