Cod sursa(job #168420)

Utilizator scvalexAlexandru Scvortov scvalex Data 31 martie 2008 12:51:20
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int N, M;
bool viz[100004];

typedef struct nod_t {  
    int n;  
    nod_t *next;  
} nod_t;  
nod_t *G[100005];  
   
void add(int u, int v) {  
    nod_t *n = new nod_t;
    n->n = v;  
    n->next = G[u];  
    G[u] = n;  
}  

void inline walk(int u) {
	viz[u] = true;
	
	for (nod_t *v = G[u]; v; v = v->next)
		if (!viz[v->n])
			walk(v->n);
}

int main(int argc, char *argv[]) {
	FILE *fi = fopen("dfs.in", "r");
	fscanf(fi, "%d %d", &N, &M);
	int u, v;
	for (int i(0); i < N; ++i) {
		fscanf(fi, "%d %d", &u, &v);
		add(u, v);
		add(v, u);
	}
	fclose(fi);
	
	int cc(0);
	for (int i(1); i <= N; ++i)
		if (!viz[i]) {
			++cc;
			walk(i);
		}
	
	ofstream fout("dfs.out");
	fout << cc << endl;
	fout.close();
	
	return 0;
}