OJ Board

Code: Select all

#include <iostream>
#include <cstdio>

using namespace std;

bool adj[3001][3001] = {false};
// Graph will be transformed into adjacently matrix.

void reset(); // Reset after each test case.

int main()
{
int t, n, m, a, b, i, j, k;

cin >> t;

while(t--) {
int triangle = 0; // The number of triangle

scanf("%d %d", &n, &m);
for(i = 1; i <= m; i++) {
scanf("%d %d", &a, &b);
adj[a][b] = true;
adj[b][a] = true;
}

// Count triangle in inputed graph.

for(i = 1; i <= m; i++) {
for(j = i + 1; j <= m; j++) {
for(k = j + 1; k <= m; k++) {
if(i != j && i != k && j != k) {
// Are I, J and K connected?
if(adj[i][j] && adj[j][k] && adj[i][k]) {
triangle++;
}
}
}
}
}

cout << triangle << endl;
}

return 0;
}

void reset()
{
int i, j;

for(i = 1; i <= 3000; i++) {
for(j = 1; j <= 3000; j++) {
adj[i][j] = false;
}
}
}