Cod sursa(job #195838)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 22 iunie 2008 02:36:24
Problema Triplete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>

#define MMAX 65537
#define NMAX 4097
struct rel{int x,y;};
rel v[MMAX];
int n,m;
int p[NMAX+1];
void poz(int st,int dr,int &piv){
int i=st,j=dr,d=0;
rel t;
while(i<j){
	if(v[i].x>v[j].x||v[i].x==v[j].x&&v[i].y>v[j].y)
		{t=v[i];v[i]=v[j];v[j]=t;d=1-d;}
	i+=d;j-=1-d;
	}
piv=i;
}

void qsrt(int li,int ls){
int piv;
if(li<ls){
	poz(li,ls,piv);
	qsrt(li,piv-1);
	qsrt(piv+1,ls);
	}
}

int main(){
freopen("triplete.in","r",stdin);
freopen("triplete.out","w",stdout);

int i,j,k,l,c,nrtr=0,t;
scanf("%d%d",&n,&m);
for(i=0;i<m;++i){
	scanf("%d%d",&l,&c);
	if(l>c) {t=l;l=c;c=t;}
	v[i].x=l;v[i].y=c;
	}
qsrt(0,m-1);

for(i=0;i<m;++i)
	if(p[v[i].x]) continue;
	else p[v[i].x]=i;
p[1]=0;
int el1,el2,el3;
for(i=0;i<m-1;++i){
	el1=v[i].x;
	el2=v[i].y;
	if(p[el2])
		for(j=p[el2];j<m&&v[j].x==el2;++j){
			el3=v[j].y;
			if(v[i+1].x==el1)
				for(k=i+1;k<m&&v[k].x==el1;++k)
					if(v[k].y==el3){
						nrtr++;
						//printf("%d%d%d\n",el1,el2,el3);
						}
				}
		}
printf("%d",nrtr);
return 0;
}