cmpcmp/p8.4dm.cpp at master · Tehada/cmpcmp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
std::vector<std::vector<int>> adjMatrix; // adjList is better
int V = adjMatrix.size();

//takes constant time if we use adjList
int deg(int vertex) {
    int ans = 0;
    for (int i = 0; i < V; ++i)
        if (adjMatrix[vertex][i]) ++ans;
    return ans;
}

//takes constant time if we use adjList
bool check_if_in_clique(int vertex) {
    for (int i = 0; i < V; ++i) {
        if (adjMatrix[vertex][i]) {
            for (int j = i; j < V; ++j)
                if (adjMatrix[i][j] && adjMatrix[vertex][j]) return true;
        }
    }
    return false;
}

int main() {
    bool ans = false;
    for (int vertex = 0; vertex < V; ++vertex) {
        if (deg(vertex) > 1 && check_if_in_clique(vertex)) {
            ans = true;
            break;
    }
    if (ans) std::cout << "YES\n";
    else std::cout << "NO\n";
}

//O(V) * [O(V) + O(V^2)] == O(V^3) adjMatrix
//O(V) * C == O(V) adjList