Pagini recente » Cod sursa (job #2324748) | Profil StefanSinkovicz | Cod sursa (job #357450) | Cod sursa (job #1586474) | Cod sursa (job #1231421)
#include <fstream>
#include <bitset>
#include <list>
#define SIZE 1000001
using namespace std;
list<int>* ADJ[SIZE];
bitset<SIZE> V;
void dfs(int n)
{
V.set(n);
list<int>* neighbors = ADJ[n];
if (neighbors)
{
for (list<int>::iterator it = neighbors->begin(); it != neighbors->end(); ++it)
{
if (!V.test(*it))
{
dfs(*it);
}
}
}
}
int main()
{
ifstream ifs("dfs.in");
ofstream ofs("dfs.out");
int n, m;
ifs >> n >> m;
for (int i = 0; i < m; ++i)
{
int x, y;
ifs >> x >> y;
if(ADJ[x] == 00)
{
ADJ[x] = new list<int>();
}
ADJ[x]->push_back(y);
}
int comp = 0;
for (int i = 1; i <= n; ++i)
{
if (!V.test(i))
{
dfs(i);
++comp;
}
}
ofs << comp;
}