Pagini recente » Cod sursa (job #1777228) | Cod sursa (job #2568612) | Cod sursa (job #698265) | Cod sursa (job #304597) | Cod sursa (job #3247963)
#include <fstream>
using namespace std;
const int N = 4096;
const int M = 65536;
const int NB = 32;
int x[M], y[M];
unsigned int a[N][N/NB+1];
int nr_biti_1(int n)
{
int nr = 0;
while (n != 0)
{
nr++;
n &= (n - 1);
}
return nr;
}
int main()
{
ifstream in("triplete.in");
ofstream out("triplete.out");
int n, m;
in >> n >> m;
for (int i = 0; i < m; i++)
{
in >> x[i] >> y[i];
x[i]--;
y[i]--;
}
for (int i = 0; i < m; i++)
{
///pentru prietenia x[i] cu y[i]
int bit = y[i] % NB;///sau y[i] & (NB-1)
a[x[i]][y[i]/NB] |= (1 << bit);///setez bitul y[i]%NB al lui a[x[i]][y[i]/NB] la 1
bit = x[i] % NB;
a[y[i]][x[i]/NB] |= (1 << bit);///setez bitul x[i]%NB al lui a[y[i]][x[i]/NB] la 1
}
int nrt = 0;///numaram tripletele facand & pe biti pentru fiecare pereche (x[i],y[i])
for (int i = 0; i < m; i++)
{
for (int j = 0; j <= n / NB; j++)
{
int intersectie = a[x[i]][j] & a[y[i]][j];
nrt += nr_biti_1(intersectie);
}
}
out << nrt / 3 << "\n";
in.close();
out.close();
return 0;
}