Cod sursa(job #7052)

Utilizator webspiderDumitru Bogdan webspider Data 21 ianuarie 2007 12:11:46
Problema Triplete Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 1.23 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

const int modn = 49999;
const int bzh  = 17;

vector<int> fii[4097];
vector<int> stuff;
int muchii[65537][2];
int intln[4097];

int hash[49999];

int n,m;
int ntrip;

int main()
{
	int i,a,b,j;
	int hsh;
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);

	scanf("%d %d\n", &n, &m);

	for ( i = 0; i < m; i++ )
	{
		scanf("%d %d\n", &a, &b);
		fii[a].push_back(b);
		fii[b].push_back(a);
		muchii[i][0] = a;
		muchii[i][1] = b;
	}
	for ( i = 1 ; i <= n ; i++ )
		sort( fii[i].begin(), fii[i].end() );
	for ( i = 0; i < m; i++ )
	{
		
		for ( j = 0; j < fii[ muchii[i][0] ].size(); j++ )
		{
			if ( binary_search( fii[ muchii[i][1] ].begin(), fii[ muchii[i][1] ].end(), fii[ muchii[i][0] ][j] ) )
			{
				stuff.clear();
				stuff.push_back( muchii[i][0] );
				stuff.push_back( muchii[i][1] );
				stuff.push_back( fii[ muchii[i][0] ][j] );

				sort( stuff.begin(), stuff.end() );
				
				hsh = ( ( bzh*bzh*stuff[0] ) % modn + ( bzh * stuff[1] ) % modn + stuff[2] ) % modn;
				
				if ( !hash[ hsh ] )
				{
					ntrip++;
					hash[ hsh ] = 1;
				}
			}
		}
	}
	
	printf("%d\n", ntrip);

	fclose(stdin);
	fclose(stdout);

	return 0;
}