Pagini recente » Borderou de evaluare (job #1151426) | Cod sursa (job #3324909) | Cod sursa (job #830280) | Atasamentele paginii Profil hrib_the_sloth | Cod sursa (job #3335596)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int N = 1e5;
vector<int> lista_ad[N + 1];
bool vizitat[N + 1];
int nr_cc = 1;
void adancime(int plecare)
{
for (int v : lista_ad[plecare])
{
// parcurgem vecinii nevizitati - in adancime
if (!vizitat[v])
{
vizitat[v] = true;
adancime(v);
}
}
}
void dfs(int n, int m)
{
for (int i = 1; i <= n; i++)
vizitat[i] = false;
vizitat[1] = true;
adancime(1);
for (int i = 1; i <= n; i++)
{
if (!vizitat[i])
{
// mai exista noduri nevizitate deci avem cel putin 2 cc
nr_cc++;
adancime(i);
}
}
}
int main()
{
int n, m;
in >> n >> m;
int u, v;
for (int i = 0; i < m; i++)
{
in >> u >> v;
lista_ad[u].push_back(v);
}
dfs(n, m);
out << nr_cc;
return 0;
}