Pagini recente » Cod sursa (job #504986) | Cod sursa (job #381969) | Cod sursa (job #2924280) | Cod sursa (job #1071215) | Cod sursa (job #971966)
Cod sursa(job #971966)
#include <fstream>
#include <stack>
#include <list>
int main(void)
{
std::ofstream out("dfs.out");
std::ifstream in("dfs.in");
int nV, nM, a, b, k;
in >> nV >> nM;
std::list<int> *arr = new std::list<int>[nV];
bool *check = new bool[nV];
for(int i = 0; i < nV; i++)
check[i] = false;
for(int i(0); i < nM; i++)
{
in >> a >> b;
a--;
b--;
arr[a].push_back(b);
arr[b].push_back(a);
}
for(int i(0); i < nV; i++)
{
if(check[i]) continue;
k++;
std::stack<int> myS;
myS.push(i);
check[i] = true;
while(!myS.empty())
{
int n = myS.top();
if(!arr[n].empty())
{
int m = arr[n].front();
arr[n].pop_front();
check[m] = true;
myS.push(m);
continue;
}
myS.pop();
}
}
out << k;
return 0;
}