Cod sursa(job #7572)

Utilizator blasterzMircea Dima blasterz Data 21 ianuarie 2007 18:08:56
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>
#include <vector>
#define maxn 4096

using namespace std;

vector<vector<int> > a;
bool viz[maxn], x[maxn][maxn];
int n, m;
long long nr;
int Q[maxn];

void citire()
{
	freopen("triplete.in", "r", stdin);
	scanf("%d %d\n", &n, &m);
	a.resize(n+1);
	for(int i=1;i<=m;i++)
	{
		int p, q;
		scanf("%d %d\n", &p, &q);
		a[p].push_back(q);
		a[q].push_back(p);
		x[p][q]=1;
		x[q][p]=1;
	}
}
void dfs(int nd, int k)
{
	//printf("%d\n", nd);
	viz[nd]=1;
	Q[k]=nd;
	int i;
	for(i=k-2;i>=1;i--)
		if(x[nd][Q[i+1]] && x[nd][Q[i]] && x[Q[i+1]][Q[i]])nr++;
	
	for(i=0;i<a[nd].size();i++)
		if(!viz[a[nd][i]]) dfs(a[nd][i], k+1);
}

int main()
{
	citire();
	for(int i=1;i<=n;i++)  dfs(i, 1);
freopen("triplete.out", "w", stdout);
	printf("%lld\n",nr);
return 0;
}