Cod sursa(job #534130)

Utilizator feelshiftFeelshift feelshift Data 15 februarie 2011 11:53:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
// http://infoarena.ro/problema/dfs
#include <cstdio>
#include <list>
using namespace std;

#define maxSize 100001

int nodes,edges,conexComponents;
list<int> graph[maxSize];
bool visited[maxSize];

void read();
void findConexComponents();
	void depthFirst(int startNode);
void write();

int main() {
	read();
	findConexComponents();
	write();

	return (0);
}

void read() {
	freopen("dfs.in","rt",stdin);
	int from,to;

	scanf("%d",&nodes);
    scanf("%d",&edges);
//	graph.resize(nodes+1);
//	visited.resize(nodes+1);

	for(int i=1;i<=edges;++i) {
		scanf("%d",&from);
        scanf("%d",&to);

		graph[from].push_back(to);
		graph[to].push_back(from);
	}

	fclose(stdin);
}

void findConexComponents() {
	for(int i=1;i<=nodes;++i)
		if(!visited[i]) {
			depthFirst(i);
			conexComponents++;
		}
}

void depthFirst(int toVisit) {
	visited[toVisit] = true;

    list<int>::iterator end = graph[toVisit].end();

	for(list<int>::iterator it=graph[toVisit].begin();it!=end;++it)
		if(!visited[*it])
			depthFirst(*it);
}

void write() {
	freopen("dfs.out","wt",stdout);

	printf("%d\n",conexComponents);

	fclose(stdout);
}