Cod sursa(job #2319079)

Utilizator AncaPocovnicuAnca Pocovnicu UVT AncaPocovnicu Data 13 ianuarie 2019 20:15:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <cstdio>
#include <vector>
#include <deque>
#include <fstream>

using namespace std;

vector <int> vec [100003];
int ok[100003];

void df(int j)
{
	while (!vec[j].empty())
		{
			if (!ok[vec[j].back()]) {
                ok[vec[j].back()] = 1;

                df(vec[j].back());
            }
			vec[j].pop_back();
		}
}

int main()
{
	int n,m,i,a,b;
	ifstream f("dfs.in");
	ofstream g("dfs.out");
	f>>n>>m;
	for (i=1;i<=m;++i)
	{
	    f>>a>>b;
		vec[a].push_back(b);vec[b].push_back(a);
	}
	for (i=1,m=0;i<=n;++i)
		if (!ok[i]) {
            ok[i] = 1;
            ++m;
            df(i);
        }
	g<<m;
return 0;
}