Pagini recente » Cod sursa (job #2773794) | Cod sursa (job #2606561) | Cod sursa (job #2927655) | Cod sursa (job #2192359) | Cod sursa (job #1124378)
/// Craciun Catalin
/// Triplete
/// Infoarena
/// PreONI 2007, Runda 1
/// www.infoarena.ro/problema/triplete
/// Parcurgere bruta: Prima metoda de rezolvare e bruta si are complexitate exponentiala: O((n*(n+1)/2)*n)
/// A doua metoda de rezolvare foloseste matricea de adiacenta
#include <fstream>
#include <iostream>
#include <bitset>
#include <cstdlib>
#define NMax1 4100
#define NMax2 605
#define MMax 65540
using namespace std;
ifstream f("triplete.in");
ofstream g("triplete.out");
int n,m;
int X[MMax], Y[MMax];
bitset<NMax1> M[NMax1];
long long triplete=0;
void parcurgereEficienta()
{
f>>m;
for (int i=1;i<=m;i++)
{
char nr[100];
f>>nr; X[i]=atoi(nr);
f>>nr; Y[i]=atoi(nr);
M[X[i]][Y[i]]=M[Y[i]][X[i]]=1;
}
f.close();
for (int i=1;i<=m;i++)
triplete+=(M[X[i]]&M[Y[i]]).count();
g<<triplete/3<<'\n';
g.close();
}
void parcurgereBruta()
{
bool A[NMax2][NMax2]; /// Matricea de adiacenta
f>>m;
for (int i=1;i<=m;i++)
{
int x,y;
f>>x>>y;
A[x][y]=A[y][x]=true;
}
f.close();
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
for (int k=j+1;k<=n;k++)
if (A[i][j] && A[j][k] && A[k][i])
triplete++;
g<<triplete<<'\n';
g.close();
}
int main()
{
f>>n;
if (n<=500)
parcurgereBruta();
else
parcurgereEficienta();
return 0;
}