Cod sursa(job #662277)

Utilizator galbenugalbenu dorin galbenu Data 16 ianuarie 2012 13:09:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
#include<cstring>
#define lmax 100002
using namespace std;
ifstream f("dfs.in",fstream::in);
ofstream g("dfs.out",fstream::out);
bool viz[lmax];
struct nod
{unsigned int inf;
 nod *urm;
};
nod *L[lmax];
unsigned int n,m;
void add(unsigned int x,unsigned int y)
{nod *nou;
 nou=new nod;
 nou->inf=x;
 nou->urm=L[y];
 L[y]=nou;
}
void DF(unsigned int i)
{viz[i]=1;
 nod *p;
  for(p=L[i];p;p=p->urm)
	   if(!viz[p->inf])
		    DF(p->inf);
}
void citire()
{unsigned int i,x,y;
 f>>n>>m;
  for(i=1;i<=m;i++)
	  f>>x>>y,add(y,x),add(x,y);
}
unsigned int  solve()
{unsigned int contor=0,i;
 for(i=1;i<=n;i++)
	  if(!viz[i])
	  {DF(i); 
	   contor+=1;
	  }
	  return contor;
}
int main()
{citire();
 //show_noduri();
 g<<solve();
 f.close();
 g.close();
 return 0;
}