Cod sursa(job #305571)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 17 aprilie 2009 20:14:08
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include<fstream>
#include<vector>

#define f first
#define s second
#define pb push_back

using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

vector<long> x[200001];
vector<int> marked(10001,0);
long i,j,m,n,k,p,s;

void dfs(int nod)
{
marked[nod]=1;

for(int i=0; i<x[nod].size(); i++)
	if(!marked[x[nod][i]])
		dfs(x[nod][i]);
}

int main()
{
in>>n>>m;
for(i=1; i<=m; i++)
	{
	in>>k>>p;
	x[k].pb(p);
	x[p].pb(k);
	}
for(i=1; i<=m; i++)
	if(!marked[i])
		{
		dfs(i);
		s++;
		}
out<<s;
}