强连通图，Tarjan——CodeForces - 427C

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+7;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
struct edge{
    int to,next;
}e[maxn*3];
int head[maxn],minc[maxn],nway[maxn],st[maxn],instack[maxn],low[maxn],dfn[maxn],cost[maxn];
int n,m,a,b,top,cnt,scc,tot;
void add(int u,int v){
    e[tot].to=v;
    e[tot].next=head[u];
    head[u]=tot++;
}
void init(){
    memset(head,-1,sizeof(head));
}
void Tarjan(int x){
    st[++top]=x;
    instack[x]=1;
    low[x]=dfn[x]=++cnt;
    for(int i=head[x];i!=-1;i=e[i].next){
        int y=e[i].to;
        if(!dfn[y]){
            Tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(instack[y])low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        int p=-1;
        scc++;
        minc[scc]=INF;
        do{
            p=st[top];
            instack[p]=0;
            if(cost[p]<minc[scc]){
                minc[scc]=cost[p];
                nway[scc]=1;
            }
            else if(cost[p]==minc[scc])
                nway[scc]++;
            top--;
        }while(st[top+1]!=x);
    }
}
void dfs(){
    for(int i=1;i<=n;i++)
        if(!dfn[i])Tarjan(i);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&cost[i]);
    scanf("%d",&m);
    init();
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    dfs();
    LL sum=0,sumn=1;
    for(int i=1;i<=scc;i++){
        sum+=minc[i];
        sumn=(sumn*nway[i])%mod;
    }
    printf("%lld %lld\n",sum,sumn);
    return 0;
}