Cod sursa(job #664408)

Utilizator arcansielAlina Bratu arcansiel Data 20 ianuarie 2012 04:31:02
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include<fstream>
using namespace std;
#define nmax 100001

struct nod{int x; nod *next;};
nod *lista[nmax];
int n,i,m,a,b,viz[nmax],nr;

void dfs() {
  for (int j=1;j<=n;j++)
    if (!viz[j]) {
	  viz[j]=1;
      for (nod *p=lista[j];p!=NULL;p=p->next)
        viz[p->x]=1;
      nr++;
    }
}   

int main() {
  ifstream f("dfs.in",ifstream::in);
  ofstream g("dfs.out",ifstream::out);
  f>>n>>m;
  for (i=0;i<m;i++) {
    f>>a>>b;
	nod *q=new nod;
	q->x=b;
	q->next=lista[a];
	lista[a]=q;
	}
  dfs();
  g<<nr;
  return 0;
}