Cod sursa(job #663644)

Utilizator XbyteAvram Florin Xbyte Data 18 ianuarie 2012 19:57:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#include<vector>

using namespace std;

#define pb push_back

const int MaxN = 100001;
const char InFile[] = "dfs.in";
const char OutFile[] = "dfs.out";

int n,m,viz[MaxN];
vector<int> G[MaxN];

void DFS(int nod)
{
	vector<int>::iterator it,iend;
	viz[nod] = 1;
	iend = G[nod].end();
	for( it = G[nod].begin() ; it != iend ; ++it )
		if( !viz[*it] )
			DFS(*it);
}

int main()
{
	ifstream fin( InFile );
	ofstream fout( OutFile );
	fin >> n >> m;
	int i,x,y;
	for( i = 0 ; i < m ; i++ )
		{
			fin >> x >> y;
			G[x].pb(y);
			G[y].pb(x);
		}
	int cnt = 0;
	for( i = 1 ; i <= n ; i++ )
		if( !viz[i] )
			{
				++cnt;
				DFS(i);
			}
	fout << cnt << '\n';
	fin.close();
	fout.close();
	return 0;
}