Cod sursa(job #675743)

Utilizator damgoodLincan Dan damgood Data 8 februarie 2012 00:50:05
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define MAXN 100001

using namespace std;

int n, m;
vector<int> g[ MAXN ];
bool vizitat[ MAXN ];

void read()
{
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	scanf("%d%d", &n, &m);
	
	int u, v;
	for(int i = 1; i <= n; ++i)
		g[i].push_back(0);
	
	for(int i = 1; i <= m; ++i)
	{
		scanf("%d%d", &u, &v);
		g[ u ].push_back( v );
	}
}

void dfs(int u)
{
	vizitat[u] = true;
	for(size_t i = 1; i <=	g[ u ].size(); ++i)
		if( !vizitat[ g[ u ][ i ] ] )
			dfs(g[ u ][ i ]);
}

void solve()
{
	int componenteConexe = 0;
	for(int i = 1; i <= n; ++i)
		if( !vizitat[i] )
		{
			dfs(i);
			++componenteConexe;
		}
	printf("%d\n", componenteConexe);
}

int main()
{
	read();
	solve();
	return 0;
}