Cod sursa(job #23490)

Utilizator damaDamaschin Mihai dama Data 28 februarie 2007 20:41:14
Problema Triplete Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#include <algorithm>

using namespace std;



int main()
{
	freopen("triplete.in","r",stdin);
	freopen("triplete.out","w",stdout);
	int n, m, *v[4096], deg[4096], x[65536], y[65536], i, cnt = 0, d1, d2;

	scanf("%d%d", &n, &m);
	
	for(i = 1; i <= m; ++i)
	{
		scanf("%d%d", &x[i], &y[i]);
		++deg[x[i]];
		++deg[y[i]];
	}
	
	for(i = 1; i <= n; ++i)
	{
		v[i] = new int[deg[i] + 1];
		v[i][0] = 0;
	}
	
	for(i = 1; i <= m; ++i)
	{
		v[x[i]][++v[x[i]][0]] = y[i];
		v[y[i]][++v[y[i]][0]] = x[i];
	}
	
	for(i = 1; i <= n; ++i)
	{
		sort(v[i] + 1, v[i] + deg[i] + 1);
	}
	
	for(i = 1; i <= m; ++i)
	{
		d1 = d2 = 1;
		while(1)
		{
			if(v[x[i]][d1] == v[y[i]][d2])
			{
				++cnt;
				if(d1 < deg[x[i]] && d2 < deg[y[i]])
				{
					++d1;
					++d2;
				}
				else
				{
					break;
				}
			}
			else if(v[x[i]][d1] > v[y[i]][d2])
			{
				if(d2 < deg[y[i]])
					++d2;
				else
					break;
			}
			else
			{
				if(d1 < deg[x[i]])
					++d1;
				else
					break;
			}
		}
	}
	
	cnt /= 3;
	
	printf("%d\n", cnt); 
	
	return 0;
}