Untitled
unknown
plain_text
a year ago
1.8 kB
2
Indexable
Never
#include <iostream> #include <cstdio> #include <stdio.h> #include <algorithm> #include <iomanip> #include <cstdlib> #include <vector> #include <set> #include <map> #include <string> #include <queue> #include <bitset> #include <cmath> #include <ctime> #define ff first #define ss second #define i1 fgvhdsjklfgh #define j1 hvfdjsklfkgh #define MAXN 500005 #define INF 1000000001LL //#define int long long using namespace std; int n, m, v, u, to, i, j, cnt[MAXN]; vector <int> g[MAXN]; long long ans; bool connected[MAXN]; bool cmp(int a, int b){ if(g[a].size() != g[b].size()) return g[a].size() < g[b].size(); return a < b; } int main(){ //freopen("input.txt", "r", stdin); ios_base :: sync_with_stdio(false); cin.tie(); scanf("%d%d", &n, &m); for(i = 0; i < m; i++){ int a, b; scanf("%d%d", &a, &b); a--; b--; g[a].push_back(b); g[b].push_back(a); } for(i = 0; i < n; i++) sort(g[i].begin(), g[i].end(), cmp); for(v = 0; v < n; v++){ for(i = 0; i < g[v].size(); i++) connected[g[v][i]] = true; for(i = 0; i < g[v].size(); i++){ u = g[v][i]; for(j = g[u].size() - 1; j >= 0; j--){ to = g[u][j]; if(cmp(to, u)) break; if(connected[to]) cnt[to]++, cnt[u]++; } } for(i = 0; i < g[v].size(); i++){ u = g[v][i]; //cout << v << " " << u << " " << cnt[u] << endl; ans += cnt[u] * 1LL * (cnt[u] - 1) / 2; cnt[u] = 0; connected[u] = false; } } //cout << ans << endl; printf("%I64d", ans / 2); return 0; }