Cod sursa(job #641627)

Utilizator florin_marius90Florin Marius Popescu florin_marius90 Data 28 noiembrie 2011 23:02:22
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;

int main()
{

	FILE * f = fopen("dfs.in", "r");
	int n, m, s;
	fscanf(f, "%i%i", &n, &m);
	vector<vector<int> > a(n);
	vector<int> viz(n);

	int i, q, w;

	for (i = 0; i < n; i++)
	{
		viz[i] = 0;
	}
	//viz[s-1] = 1;
	for (i = 0; i < m; i++)
	{
		fscanf(f, "%i%i", &q, &w);
		a[q-1].push_back(w-1);
		a[w-1].push_back(q-1);
		
	}

	fclose(f);
	stack<int> coada;
	
	int conex = 0;
	for (int k = 0; k < n; k++)
	{
        if (viz[k] == 0)
        {
                   conex++;
                   viz[k] = 1;
	               coada.push(i);

                	while(!coada.empty())
                	{
                		int e = coada.front();
                		coada.pop();
                
                		int len = a[e].size();
                		for (i = 0; i < len; i++)
                		{
                			if (viz[a[e][i]] == 0)
                			{
                				coada.push(a[e][i]);
                				viz[a[e][i]] = viz[e] + 1;
                			}
                		}
                	}
          }
    }

	f = fopen("dfs.out", "w");
	fprintf(f,"%i", conex);
	fclose(f);
	return 0;

}