tarjan强连通缩点——cf711D

电玩女神 2023-10-12 08:19 14阅读 0赞

模板题

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define N 500005
    #define mod 1000000007
    int n,a[N];
    vector<int>G[N];
    int cnt,dfn[N],low[N],ind,stk[N],ins[N],top;
    vector<int>scc[N];
    void tarjan(int x){
        dfn[x]=low[x]=++ind;
        stk[++top]=x,ins[x]=1;
        for(int i=0;i<G[x].size();i++){
            int y=G[x][i];
            if(!dfn[y]){
                tarjan(y);
                low[x]=min(low[x],low[y]);
            }
            else if(ins[y])
                low[x]=min(low[x],low[y]);
        }
        if(dfn[x]==low[x]){
            cnt++;int y;
            do{
                y=stk[top--];
                ins[y]=0;
                scc[cnt].push_back(y);
            }while(y!=x);
        } 
    }
    ll Pow(ll a,ll b){
        ll res=1;
        while(b){
            if(b%2)
                res=res*a%mod;
            b>>=1;a=a*a%mod;
        }
        return res;
    }
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            G[i].push_back(a[i]);
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                tarjan(i);
        
        ll ans=1;
        for(int i=1;i<=cnt;i++)
            if(scc[i].size()!=1)
                ans=ans*(Pow(2,scc[i].size())-2+mod)%mod;
            else ans=ans*2%mod;
        cout<<ans<<'\n';
    }

转载于:https://www.cnblogs.com/zsben991126/p/11432798.html

发表评论取消回复

表情：

评论列表（有 0 条评论，14人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ2186 Popular Cows 【强连通分量】+【Kosaraju】+【Tarjan】

/ Popular Cows （ POJ No.2186）每头牛都想成为牛群中的红人。给定 N 头牛的牛群和 M 个有序对(A, B)。 (A, B)

怼烎@/ 2024年02月17日 21:29/ 0 赞/ 51 阅读

相关 tarjan强连通缩点——cf711D

模板题 include<bits/stdc++.h> using namespace std; define ll long long def

电玩女神/ 2023年10月12日 08:19/ 0 赞/ 15 阅读

相关 P1262 间谍网络（Tarjan 求强连通分量）

题目传送门：[https://www.luogu.com.cn/problem/P1262][https_www.luogu.com.cn_problem_P1262] 题

雨点打透心脏的1/2处/ 2022年12月31日 01:29/ 0 赞/ 138 阅读

相关 HDU 1269(tarjan求强连通)

include <cstdio> include <cstring> include <algorithm> include <stack

比眉伴天荒/ 2022年09月20日 12:42/ 0 赞/ 157 阅读

相关 poj 2186 强连通分量缩点+判断出度

Popular Cows <table> <tbody> <tr> <td><strong>Time Limit:</strong> 2000MS</td>

旧城等待，/ 2022年08月20日 06:16/ 0 赞/ 164 阅读

相关【日常学习】【强连通分量tarjan缩点】codevs1611 抢掠计划题解

题目描述 Description Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定，在每个路口都设立了一个Siruseri 银行的ATM 取

矫情吗；*/ 2022年08月09日 09:14/ 0 赞/ 130 阅读

相关 201509-4 ccf 高速公路（强连通分量 tarjan算法）

题目链接： [高速公路][Link 1] 题目大意：中文题，不解释解题思路：抽象出来，其实就是求强连通分量，求出每个强连通分量的点的个数后，点对的个数就是

不念不忘少年蓝@/ 2022年05月14日 02:58/ 0 赞/ 189 阅读

相关 POJ 2186 Popular Cows——————(Kosaraju求强连通分量,缩点)

[Popular Cows][] Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 42216 Ac

╰+哭是因爲堅強的太久メ/ 2022年02月01日 14:29/ 0 赞/ 176 阅读

相关 POJ-2186-Popular Cows（强连通分量，缩点）

链接：[https://vjudge.net/problem/POJ-2186][https_vjudge.net_problem_POJ-2186] 题意：有N

Dear 丶/ 2021年12月23日 11:34/ 0 赞/ 206 阅读

相关图之强连通、强连通图、强连通分量 Tarjan算法

一、解释在有向图G中，如果两个顶点间至少存在一条互相可达路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连

秒速五厘米/ 2021年09月14日 03:12/ 0 赞/ 569 阅读