Đếm đồ thị con

Submit solution
Points: 2.5 (partial)
Time limit: 1.0s
Memory limit: 10M
Problem type
Allowed languages
C++, C11, DART, F95, GAS32, Itercal, java, kotlin, LEAN, LISP, MONOVB, PIKE, prolog, RUST, SWIFT, TUR, V8JS, VB, ZIG

Cho một đồ thị có hướng, nhiệm vụ của bạn là hãy đếm các đồ thị con có 4 đỉnh với hình dạng như sau

Input

  • Dòng đầu chứa hai số nguyên \(n, m\) là số đỉnh và số cạnh \((1 \le n, m \le 30000)\)
  • m dòng tiếp theo mỗi dòng có hai số \(u, v\) với ý nghĩa có cạnh nối từ đỉnh \(u\) tới đỉnh \(v\) \((1 \le u, v \le 30000)\)

Output

  • Một dòng duy nhất là số đồ thị con

Example

Input

5 4
1 2
2 3
1 4
4 3

Output

1

Comments


  • 1
    old_creator  commented on Aug. 6, 2022, 5:26 p.m. ← edit 8

    Code tham khảo:

    #include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    unordered_map<int, int> mp;
    vector<vector<int>> adj;
    int n, m, u, v, res= 0;
    cin >> n >> m;
    adj.resize(n);
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        u--, v--;  //Vertices: 0, 1, 2, 3,...
        adj[u].push_back(v);
    }   
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < adj[i].size(); j++)
            for(int k = 0; k < adj[adj[i][j]].size(); k++)
                mp[adj[adj[i][j]][k]]++;
        for(auto x: mp) 
            res += x.second*(x.second - 1)/2;
        mp.clear(); 
    }
    cout << res;
    return 0;
}

    ĐPT thời gian \(O(n + m^2/n)\). ĐPT không gian \(O(n + m)\).


  • 1
    TICHPX  commented on Dec. 17, 2018, 11:20 a.m.

    Bình phương ma trận