#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int MAXN = 100'001, MAXM = 200'001;
int n, m;
vector<int> adj[MAXN];
int sz[MAXN], tin[MAXN], low[MAXN], par[MAXN];
bool vis[MAXN];
bool dfs(int u1, int u2, vector<bool> &vis, int target) {
if (u1 == target && u2 == target) {
return true;
}
if (u1 != target) vis[u1] = true;
if (u2 != target) vis[u2] = true;
if (u1 == target && u2 != target) {
for (int v2 : adj[u2]) {
if (vis[v2]) continue;
if (dfs(u1, v2, vis, target)) return true;
}
} else if (u1 != target && u2 == target) {
for (int v1 : adj[u1]) {
if (vis[v1]) continue;
if (dfs(v1, u2, vis, target)) return true;
}
} else {
for (int v1 : adj[u1]) {
if (vis[v1]) continue;
for (int v2 : adj[u2]) {
if (vis[v2]) continue;
if (v1 == v2 && v1 != target) continue;
if (dfs(v1, v2, vis, target)) return true;
}
}
}
if (u1 != target) vis[u1] = false;
if (u2 != target) vis[u2] = false;
return false;
}
signed main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int ways = 0;
for (int s = 1; s <= n; s++) {
for (int c = 1; c <= n; c++) {
if (c == s) continue;
for (int f = 1; f <= n; f++) {
if (f == c || f == s) continue;
vector<bool> vis(n+1, false);
if (dfs(s, f, vis, c)) {
ways++;
// cout << "(" << s << ", " << c << ", " << f << ") works\n";
}
}
}
}
cout << ways;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |