Cod sursa(job #27919)

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

void citire(){
     FILE *in;
     long i,x,y;
     in=fopen("triplete.in","r");
     fscanf(in,"%ld %ld",&n,&m);
     for(i=1;i<=m;i++){
       fscanf(in,"%ld %ld",&x,&y);
       muc[i][0]=x;muc[i][1]=y;
       mat[x][y]=1;mat[y][x]=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(j==muc[i][0]||j==muc[i][1]) continue;
            if(mat[muc[i][0]][j]&&mat[muc[i][1]][j]) solutie++;
                          }

                 }
}
void scriere(){
     FILE *out;
     out=fopen("triplete.out","w");
     fprintf(out,"%ld",solutie/3);
     }

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