Cod sursa(job #1613070)

Utilizator pl4y0nHodorogea Alexandru pl4y0n Data 25 februarie 2016 10:38:03
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

vector<vector <int> > graf;
vector<bool> vis;
int m,n;

void dfs(int vert)
{
	if(vert<0 || vert>n-1)
		return;
	stack<int> s;
	int element,i;
	bool found;
	s.push(vert);
	vis[vert]=true;
	while(!s.empty())
	{
		element=s.top();
		found=false;
		for(i=0; i<graf[element][i] && !found;i++)
		{
			if(!vis[graf[element][i]])
				found=true;
		}
		if(found)
		{
			i--;
			s.push(graf[element][i]);
			vis[graf[element][i]]=true;
		}
		else
			s.pop();
	}
}

int main()
{
    ifstream in("dfs.in");
	in>>n>>m;
	graf.resize(n);
	vis.resize(n,false);
	int x,y,k=0;
	for(int i=0;i<m;i++)
	{
		in>>x>>y;
		x--;
		y--;
		graf[x].push_back(y);
		graf[y].push_back(x);
	}

	for(int i=0;i<vis.size() && i<n;i++)
	{
		if(!vis[i])
		{
		    k++;
            if(!graf[i].empty())
                dfs(i);
            else
                vis[i]=true;
		}
	}
    ofstream out("dfs.out");
	out<<k;
    return 0;
}