Cod sursa(job #7762)

Utilizator raula_sanChis Raoul raula_san Data 22 ianuarie 2007 16:39:52
Problema Triplete Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include<cstdio>

#define dim1 1 << 12
#define dim2 1 << 16

struct nod
{
       int info;
       nod *next;
} *L[dim1];

int N, a[dim2], b[dim2], d[dim1];

long M;

long long unsigned SOL;

void add(nod *&L, int nd)
{
     nod *camp = new nod;
     camp -> info = nd;
     camp -> next = L;
     L = camp;
}

void read()
{
     freopen("triplete.in", "r", stdin);
     
     scanf("%d %ld", &N, &M);

     long i;
     
     for(i=1; i<=M; ++i)
     {
              scanf("%d %d", a + i, b + i);
              -- a[i]; -- b[i];
              add(L[a[i]], b[i]);
              add(L[b[i]], a[i]);
              
              ++ d[a[i]]; ++ d[b[i]];
     }
}

void elimina(nod *&L, int nd)
{
     nod *camp = L, *prec = NULL;
     
	 if(L -> info == nd)
	 {
		 camp = L;
		 L = L -> next;
		 delete camp;
	 }
	 
	 else
     while(camp)
     {
                if(camp -> info == nd)
                {
						prec -> next = camp -> next;
						delete camp;
						camp = prec;
                }
                
                prec = camp;
                camp = camp -> next;
     }
}

int search(nod *L, int nd1, int nd2)
{
	int ok = 0;
	while(L)
	{
			if(L -> info == nd1)
				 ++ ok;
			if(L -> info == nd2)
				 ++ ok;

			if(ok == 2)
				  return 1;

			L = L -> next;
    }
    
    return 0;
}

void solve()
{
     long i; int nd;
     
     for(i=1; i<=M; ++i)
     {
              if(d[a[i]] >= 2 && d[b[i]] >= 2)
              {
                         for(nd=0; nd<N; ++nd)
                                   if(nd != a[i] && nd != b[i] && search(L[nd], a[i], b[i]))
                                         ++ SOL;
              }
     
              elimina(L[a[i]], b[i]);
              elimina(L[b[i]], a[i]);
              
              -- d[a[i]]; -- d[b[i]];
     }
}

void write()
{
     freopen("triplete.out", "w", stdout);
     
     printf("%llu", SOL);
}

int main()
{
    read();
    solve();
    write();
    
    fclose(stdin); fclose(stdout);
    return 0;
}