Cod sursa(job #846430)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 2 ianuarie 2013 10:03:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const char iname[] = "dfs.in";
const char oname[] = "dfs.out";
ifstream fin(iname);
ofstream fout(oname);
int N , M , i , j , x , y , comp_conexe , gasit;
bool viz[ 100004 ];
vector < int > Q[ 100004 ];
stack < int > st;
int main()
{
	fin >> N >> M;
	for (i = 1; i <= M; ++i)
		fin >> x >> y , Q[x].push_back(y) , Q[y].push_back(x);
	vector < int > :: iterator it;
	for (i = 1; i <= N; ++i)
	{
		if (!viz[i])
		{
			viz[i] = 1;
			st.push(i);
			while(!st.empty())
			{
				x = st.top();
				gasit = 0;
				while(!Q[x].empty())
				{
					if (!viz[Q[x].front()])
					{
						it = Q[x].begin();
						st.push(*it);
						viz[*it] = 1;
						Q[x].erase(Q[x].begin());
						gasit = 1;
						break;
					}
					else
						Q[x].erase(Q[x].begin());
				}
				if (!gasit)
					st.pop();
			}
			++comp_conexe;
		}
	}
	fout << comp_conexe << '\n';
	return 0;
}