Pagini recente » Istoria paginii runda/14pb_simple/clasament | preoni-2007/runda-finala/poze/premiere | Monitorul de evaluare | Istoria paginii runda/fara_nume/clasament | Cod sursa (job #2431548)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<int> lista[100010];
bool viz[100010];
void addVertex(int x,int y)
{
lista[x].push_back(y);
lista[y].push_back(x);
}
void dfs(int start)
{
stack<int> stac;
stac.push(start);
viz[start]=true;
while(stac.size())
{
int current = stac.top();
for(int i = 0;i<lista[current].size();i++)
{
if(viz[lista[current][i]]==false)
{
viz[lista[current][i]]=true;
stac.push(lista[current][i]);
}
}
stac.pop();
}
}
int main()
{
int n,m,x,y,counter=0;
fin>>n>>m;
for(int i = 1;i<=m;i++) fin>>x>>y,addVertex(x,y);
for(int i =1;i<=n;i++)
{
if(viz[i]==false)
{
counter++;
dfs(i);
}
}
fout<<counter<<'\n';
return 0;
}