Cod sursa(job #662242)

Utilizator galbenugalbenu dorin galbenu Data 16 ianuarie 2012 10:50:41
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<iostream>
#include<fstream>
#include<cstring>
#define nmax 100005
#define mmax 500005
using namespace std;
ifstream f("dfs.in",fstream::in);
ofstream g("dfs.out",fstream::out);
typedef struct
{unsigned int inc,sf;}muchie;
muchie m[mmax];
unsigned int l[nmax];
unsigned int n,mm,distinct[nmax];
void read()
{f>>n>>mm;
 for(unsigned int i=1;i<=mm;i++)
	  f>>m[i].inc>>m[i].sf;
}
void init()
{for(unsigned int i=1;i<=n;i++)
	 l[i]=i;
}
void kruskal()
{unsigned int xx,j,yy,k=1,i=1;
 while(k<n && i<=mm)
 {if(l[m[i].inc]!=l[m[i].sf])
 {k++;
  xx=l[m[i].sf];
  yy=l[m[i].inc];
   for(j=1;j<=n;j++)
	   if(l[j]==xx)
		   l[j]=yy;
 }
 i++;
 }
}
 void show_l()
 {unsigned int i;
  for(i=1;i<=n;i++)
	  cout<<l[i]<<" ";
cout<<"\n";
 }
unsigned int solve()
 {unsigned int  nrdistinct=0; 
  unsigned int i,j;
  bool q;
   for(i=1;i<=n;i++)
	 {  q=1;
		 for(j=1;j<=nrdistinct;j++)
		  if(distinct[j]==l[i])
			  q=0;
		  if(q)
			  distinct[++nrdistinct]=l[i];
	 }
return nrdistinct;
 }	   
 int main()
 {read();
  init();
  //show_l();
  kruskal();
 // show_l();
  g<<solve();
  f.close();
  g.close();
  return 0;
 }