#include<bits/stdc++.h>
#define mid (((l)+(r))/2)
using namespace std;
typedef long long ll;
typedef long double ld;
const ll N=1e5+10,inf=1e18+10,mod=1e9+7;
ll n,m,a[N],tot,dfn[N],low[N];
bool ins[N];
vector<ll> G[N];
stack<ll> sta;
vector<vector<ll> > scc;
void tarjan(ll u){
dfn[u]=low[u]=++tot,sta.push(u),ins[u]=true;
for(auto v:G[u]){
if(!dfn[v])tarjan(v);
if(ins[v])low[u]=min(low[u],low[v]);
}
if(low[u]==dfn[u]){
scc.push_back(vector<ll>());
while(ins[u])ins[sta.top()]=false,scc.back().push_back(sta.top()),sta.pop();
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n;
for(ll i=1;i<=n;i++)cin >> a[i];
cin >> m;
for(ll i=1;i<=m;i++){
ll u,v;
cin >> u >> v;
G[u].push_back(v);
}
for(ll i=1;i<=n;i++)if(!dfn[i])tarjan(i);
ll cost=0,ans=1;
for(auto i:scc){
ll l=inf,cnt=0;
for(auto j:i)l=min(l,a[j]);
for(auto j:i)if(a[j]==l)cnt++;
cost+=l,ans*=cnt,ans%=mod;
}
cout << cost << ' ' << ans;
return 0;
}
标签:连通,sta,ll,back,ins,dfn,low,分量
From: https://www.cnblogs.com/alric/p/18342817