Pagini recente » Cod sursa (job #1441444) | Diferente pentru documentatie/arhiva-educationala intre reviziile 3 si 2 | Cod sursa (job #1478466) | Cod sursa (job #2085161) | Cod sursa (job #2280678)
#include <fstream>
#include <vector>
#define NMAX 200005
using namespace std;
ifstream in ("dfs.in");
ofstream out ("dfs.out");
int n,m;
bool vizitat[NMAX];
int answer;
struct Nod
{
int curent;
Nod* urm;
};
typedef Nod* PNod;
PNod muchii[NMAX];
PNod final_muchii[NMAX];
void adauga(int i,int j)
{
if(muchii[i]==NULL){
muchii[i]=new Nod;
muchii[i]->urm=NULL;
muchii[i]->curent=j;
final_muchii[i]=muchii[i];
}
else{
PNod aux=new Nod;
aux->curent=j;
final_muchii[i]->urm=aux;
aux->urm=NULL;
final_muchii[i]=aux;
}
}
void DFS(int x)
{
vizitat[x]=true;
int nod_curent;
if(muchii[x]!=NULL){
for(PNod i=muchii[x];i!=NULL;i=i->urm){
nod_curent=i->curent;
if(!vizitat[nod_curent]){
DFS(nod_curent);
}
}
}
}
int main()
{
int i,x,y;
in>>n>>m;
for(i=1;i<=m;i++){
in>>x>>y;
adauga(x,y);
adauga(y,x);
}
for(i=1;i<=n;i++){
if(!vizitat[i]){
answer++;
DFS(i);
}
}
out<<answer;
return 0;
}