Cod sursa(job #27892)

Utilizator AdixSuciu Adrian Adix Data 7 martie 2007 11:30:07
Problema Triplete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
long m,n,muc[70000][2],solutie;

void citire(){
     FILE *in;
     long i;
     in=fopen("triplete.in","r");
     fscanf(in,"%ld %ld",&n,&m);
     for(i=1;i<=m;i++){
       fscanf(in,"%ld %ld",&muc[i][0],&muc[i][1]);
                       }
     }

int existamuchie(long i,long j,long ii){
long k;
		 for(k=ii+1;k<=m;k++){
              if((muc[k][0]==i&&muc[k][1]==j)
              ||(muc[k][1]==i&&muc[k][0]==j))
              	return 1;
		 }
     return 0;
     }
     

void procesare(){
long i,j;
/*
Pentru o muchie fixata este suficienta iterarea prin lista de adiacenta a 
nodurilor a si b si adunarea la numarul total de solutii a numarului de 
noduri comune. Acest algoritm are complexitatea O(M * N), 
pentru ca parcurgerea unei liste de adiacenta se realizeaza in O(N)
*/
for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
		if(muc[i][0]==j||muc[i][1]==j) continue;
		 if(existamuchie(muc[i][0],j,i)&&existamuchie(muc[i][1],j,i))solutie++;
            }
   }
}
void scriere(){
     FILE *out;
     out=fopen("triplete.out","w");
     fprintf(out,"%ld",solutie);
     }

int main(){
     citire();
     procesare();
     scriere();
     return 0;
     
     }