Untitled
unknown
plain_text
2 years ago
1.8 kB
9
Indexable
#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;
}
Editor is loading...