C. Checkposts

https://codeforces.com/contest/427/problem/C

题意：给个图，每个点是一个junction，在junction可以建立一个checkpost，不同的junction建立checkpost有不同的代价。但是如果两个junction是强连通的，那么可以在这两个junction中任意建立一个。
求建立checkpost的最小代价，以及在当前最小代价下，有多少种建立checkpost的方式。

思路：tarjan算法求强连通分量，然后对每个分量遍历，找出最小的代价和对应的数量，累计到答案中即可。

总结：第一次写图中的强连通分量题目，目前对图的掌握还停留在邻接表的dfs或者bfs，或者简单的dp中。。tarjan算法的核心思想是，如果当前点没有被访问，则dfs。在dfs过程中记录一个low和一个dfn数组，这两个数组分别记录了最小访问时间戳和正常访问时间戳。并且还需要一个栈。当low和dfn的值相等时，当前点就是一个连通分量的头节点，在栈中比这个点高的点就是连通分量中的其他节点。

class Tarjan{
public:
    Tarjan(const vector<vector<int>>& s):
        sz_((int)s.size()),
        al_(s),
        low_(sz_, -1),
        dfn_(sz_, -1),
        in_stack_(sz_, false),
        timer_(0){}

    //strongly connected component
    vector<vector<int>> getScc(){
        for (int i = 0; i < sz_; ++i){
            if (dfn_[i] == -1){
                dfsScc(i);
            }
        }
        return components_;
    }


private:
    int sz_;
    vector<vector<int>> al_;
    vector<vector<int>> components_;
    vector<int> low_;
    vector<int> dfn_;
    vector<bool> in_stack_;
    stack<int> stk_;
    int timer_;

    void dfsScc(int u){
        low_[u] = dfn_[u] = timer_ ++;
        in_stack_[u] = true;
        stk_.push(u);
        for (const auto& v : al_[u]){
            if (dfn_[v] == -1){
                dfsScc(v);
                low_[u] = min(low_[u], low_[v]);
            }
            else if (in_stack_[v] == true){
                low_[u] = min(low_[u], low_[v]);
            }
        }
        //head of strongly connected component
        if (low_[u] == dfn_[u]){
            components_.emplace_back();
            while (!stk_.empty()){
                int cur = stk_.top();
                stk_.pop();
                components_.back().emplace_back(cur);
                in_stack_[cur] = false;
                if (cur == u){
                    break;
                }
            }
        }
    }


};
void preProcess(){

}



constexpr int mod = 1e9 + 7;
void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for (auto& x : a){
        cin >> x;
    }

    int m;
    cin >> m;

    vector<vector<int>> al(n);
    for (int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        u --;
        v --;
        al[u].emplace_back(v);
    }

    Tarjan tarjan(al);

    auto components = tarjan.getScc();

    pair<long long, long long> ans{0ll, 1ll};
    for (const auto& comp : components){
        long long cost = (long long)1e18;
        long long cnt = 1;
        for (const auto& cur : comp){
            if (checkMin(cost, a[cur])){
                cnt = 1;
            }
            else if (cost == a[cur]){
                cnt ++;
            }
        }
        ans.first += cost;
        ans.second = ans.second * cnt % mod;
    }

    cout << ans.first << ' ' << ans.second << '\n';
}