Cod sursa(job #802378)

Utilizator dm1sevenDan Marius dm1seven Data 26 octombrie 2012 16:08:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

//int e_014_dfs()
int main()
{
	string in_file = "dfs.in";
	string out_file = "dfs.out";

	const int MAX_N = 100000;

	int n;
	int m;

	vector<int> adj_lists[MAX_N + 1];
	
	int component[MAX_N + 1];
	
	ifstream ifs(in_file.c_str());
	ifs>>n>>m;
	//read the edges and fill the adjacency list
	for (int e = 1; e <= m; e++) 
	{
		int v1, v2;
		ifs>>v1>>v2;
		adj_lists[v1].push_back(v2);
		adj_lists[v2].push_back(v1);
	}
	ifs.close();

	for (int v = 1; v <= n; v++) component[v] = -1;

	int last_component_val = 0;
	queue<int> Q;
	
	for (int v = 1; v <= n; v++)
	{
		if (component[v] == -1)
		{
			Q.push(v);
			component[v] = (++last_component_val);
	
			while ( !Q.empty() )
			{
				int u = Q.front();
				Q.pop();			
				for (vector<int>::iterator it = adj_lists[u].begin(); it != adj_lists[u].end(); it++)
				{
					int s = *it;
					if (component[s] == -1)//if not processed and not in queue
					{
						Q.push(s);
						component[s] = last_component_val;
					}
				}
			}
		}		
	}

	ofstream ofs(out_file.c_str());
	ofs<<last_component_val;
	ofs.close();

	return 0;
}