Cod sursa(job #664408)
Utilizator | Alina 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;
}