GraphRGB

2 secs 1024 MB

頂点Gに注目します。R -> G および G -> B という経路を見つけることが目標となります。したがって、各頂点Gに隣接する頂点Rの数を $x$ 、頂点Bの数を $y$ とします。各頂点Gについて、 $x \times y$ の値をすべて合計すると、求める経路の数になります。

この解法での計算量は各頂点に隣接する全ノードを探索する事から計算量は $O(N+M)$ となります。

実装

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
​
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> to(n);
    for(int i = 0;i < m; ++i){
        int u, v;
        cin >> u >> v;
        --u; --v;
        to[u].push_back(v);
        to[v].push_back(u);
    }
    string s;
    cin >> s;
​
    long ans = 0;
    for(int i = 0;i < n; ++i){
        if(s[i] == 'G'){
            long count_r = 0, count_b = 0;
            for(int v: to[i]){
                if(s[v] == 'R'){
                    count_r++;
                }
                if(s[v] == 'B'){
                    count_b++;
                }
            }
            ans += count_r * count_b;
        }
    }
​
    cout << ans << endl;
    return 0;
}

GraphRGB

解説

実装