Cod sursa(job #1609946)

Utilizator kasperDorin Puscasu kasper Data 23 februarie 2016 10:22:53
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
// parcurgerea in latime lista de adiacenta

#include<bits/stdc++.h>
#define in "dfs.in"
#define out "dfs.out"
#define Max 100000

using namespace std;

ifstream fin(in);
ofstream fout(out);

typedef struct nod{
	int inf;
	nod *next;
}*lista;

int n,m,i,j,x,y;

lista lda[Max];
bool viz[Max];

void add(lista &y,int x)
{
	lista q=new nod;
	q->inf=x;
	q->next=y;
	y=q;
}

void dfs(int x)
{
	viz[x]=1;
	for(lista p=lda[x];p;p=p->next)
    if(!viz[p->inf])
		dfs(p->inf);
}


int main()
{
  fin>>n>>m;
  while(m--)
  {
    fin>>x>>y;
    add(lda[y],x);
    add(lda[x],y);
  }
  int k=0;
  for(i=1;i<=n;i++)
  if(viz[i]==0) k++,dfs(i);
  fout<<k;
 return 0;
}