Pagini recente » Cod sursa (job #2059058) | Cod sursa (job #1541356) | Cod sursa (job #2387445) | Cod sursa (job #1743492) | Cod sursa (job #28080)
Cod sursa(job #28080)
#include <stdio.h>
#include <math.h>
long m,n;
long long solutie;
int muc[65537][2];
long long mat[4098];
void citire(){
FILE *in;
long i,x,y;
in=fopen("triplete.in","r");
fscanf(in,"%ld %ld",&n,&m);
for(i=0;i<m;i++){
fscanf(in,"%ld %ld",&x,&y);
x--;
y--;
muc[i][0]=x;muc[i][1]=y;
mat[x]+=pow(2,y);
mat[y]+=pow(2,x);
}
fclose(in);
}
long formula(long k,long l){
long x,i,j;
x=mat[k]&mat[l];
i=n;j=0;
while(x!=0){
if((x-pow(2,i))>=0){ j++;x=x-pow(2,i);}
i--;
}
return j;
}
void procesare(){
long i,k,l;
/*
Pentru o muchie fixata este suficienta iterarea prin lista de adiacenta a
nodurilor a si b si adunarea la numarul total de solutii a numarului de
noduri comune. Acest algoritm are complexitatea O(M * N),
pentru ca parcurgerea unei liste de adiacenta se realizeaza in O(N)
*/
for(i=0;i<m;i++){
// for(j=1;j<=n;j++){
// if(j==muc[i][0]||j==muc[i][1]) continue;
k=muc[i][0];
l=muc[i][1];
solutie+=formula(k,l);
}
}
void scriere(){
FILE *out;
out=fopen("triplete.out","w");
fprintf(out,"%lld",solutie/3);
fclose(out);
}
int main(){
citire();
procesare();
scriere();
return 0;
}