Pagini recente » Cod sursa (job #452483) | Cod sursa (job #1303788) | Cod sursa (job #492292) | Cod sursa (job #2666130) | Cod sursa (job #1298716)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f ("triplete.in");
ofstream g ("triplete.out");
const int NMAX = 4096 + 1, MMAX = 65536 + 1;
int n, m;
pair <int, int> muchie[NMAX];
vector <int> graf[NMAX];
void citeste() {
f >> n >> m;
int a, b;
for (int i = 1; i <= m; i++) {
f >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
muchie[i] = make_pair(a, b);
}
}
void rezolva() {
int x, y;
long long sol = 0;
vector <int> :: iterator it1, it2, end1, end2;
for (int i = 1; i <= m; i++) {
x = muchie[i].first;
y = muchie[i].second;
end1 = graf[x].end();
end2 = graf[y].end();
it1 = graf[x].begin();
it2 = graf[y].begin();
while (it1 != end1 && it2 != end2) {
if (it2 != end2)
while (it1 != end1 && *it1 < *it2) it1++;
if (it1 != end1)
while (it2 != end2 && *it2 < *it1) it2++;
if (it1 != end1 && it2 != end2)
if (*it1 == *it2) {sol++; it1++; it2++;}
}
for(i=1;i<=m;i++){
x=b[i][0];
y=b[i][1];
end1=a[x].end();
it1=a[x].begin();
end2=a[y].end();
it2=a[y].begin();
while(it1!=end1 && it2!=end2){
if(it2!=end2)
while(it1!=end1 && *it1 < *it2) it1++;
if(it1!=end1)
while(it2!=end2 && *it2 < *it1) it2++;
if(it1!=end1 && it2!=end2)
if(*it1==*it2) {nr++;it1++;it2++;}}}
}
sol /= 3;
g << sol << '\n';
}
int main() {
citeste();
for (int i = 1; i <= n; i++) sort(graf[i].begin(), graf[i].end());
rezolva();
return 0;
}