Skip to content

Instantly share code, notes, and snippets.

@ch-hristov
Created August 29, 2015 18:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ch-hristov/1453a09e72832598d6e1 to your computer and use it in GitHub Desktop.
Save ch-hristov/1453a09e72832598d6e1 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <stdio.h>
#include <tuple>
#include <stack>
#include <queue>
using namespace std;
int edges[4100];
int graph[4100][4100];
int f, s;
int vis[4100];
int prev;
long ans = 9999999999;
bool flag = 0;
int getDiff(int a, int m, int diff1, int diff2) {
int c = 0;
for (int i = 1; i <= m; i++) {
if (i != diff1 && i != diff2) {
if (graph[a][i]) {
c++;
}
}
}
return c;
}
void dfs(int prev, int cur, int m) {
vis[cur] = 1;
for (int i = 1; i <= m; i++) {
if (graph[cur][i] > 0 && vis[i] && i != prev && prev != -1) {
int edges = getDiff(prev, m, cur, i);
int edges2 = getDiff(cur, m, prev, i);
int edges3 = getDiff(i, m, cur, prev);
int j = edges + edges2 + edges3;
if (j < ans) {
ans = j;
}
flag = 1;
}
else {
if (!vis[i]) {
dfs(cur, i, m);
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> f >> s;
graph[f][s] = 1;
graph[s][f] = 1;
edges[f]++;
edges[s]++;
}
for (int i = 0; i < n; i++) {
if (!vis[i + 1]) {
dfs(-1, i + 1, m);
}
}
if (ans == 999999999)
cout << -1 << endl;
else
cout << ans << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment