Pagini recente » Cod sursa (job #1185729) | Cod sursa (job #1090098) | Cod sursa (job #321229) | Cod sursa (job #2221273) | Cod sursa (job #2379832)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("triplete.in");
ofstream fout("triplete.out");
struct elem{int un,doi;}; elem v[131075];
bool compar(elem a1, elem a2){if(a1.un>a2.un)return 0; else if(a1.un<a2.un)return 1; if(a1.doi>a2.doi)return 0; if(a1.doi<a2.doi)return 1; return 1;}
long long i,N,M,poz[4100],poz2[4100],a,b,y,j,st,dr,m,ok,nr;
int main()
{
fin>>N>>M;
for(i=1;i<=M;i++){ fin>>a>>b;
v[++y].un=a; v[y].doi=b;
v[++y].un=b; v[y].doi=a;
}
sort(v+1,v+y+1,compar);
// for(i=1;i<=y;i++)fout<<v[i].un<<" "<<v[i].doi<<'\n'; fout<<'\n';
for(i=1;i<=y;i++){
if(!poz[v[i].un])poz[v[i].un]=i;
poz2[v[i].un]=i;
}
// for(i=1;i<=4;i++)fout<<poz[i]<<" "<<poz2[i]<<'\n'; fout<<'\n';
for(i=1;i<=y;i++){
while(v[i].un>v[i].doi)i++;
if(i<=M){ j=i+1;
//verificare ptr cand prima din pereche e aceeasi
while(v[i].un==v[j].un){
// fout<<i<<" "<<j<<'\n';
st=poz[v[i].doi]; dr=poz2[v[i].doi]; ok=0;
// fout<<st<<" "<<dr<<'\n';
while(st<=dr){ m=(st+dr)/2;
if(v[m].doi<v[j].doi)st=m+1;
else if(v[m].doi>v[j].doi)dr=m-1;
else {ok=1; break;}
}
if(ok)nr++;
j++;
}
//
}
}
fout<<nr;
return 0;
}