Pagini recente » Cod sursa (job #2520248) | Cod sursa (job #2675572) | Cod sursa (job #1803851) | Cod sursa (job #2850485) | Cod sursa (job #2797177)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
FILE *fin, *fout;
int N, M, x, y, nrComp;
const int NMAX=100001;
vector <int>graph[NMAX];
bool found[NMAX];
void dfs(){
stack <int> s;
nrComp=0;
int current;
for(int nod=1;nod<=N;nod++){
if(found[nod]==false){
nrComp++;
s.push(nod);
found[nod]=true;
while(!s.empty()){
current=s.top();
s.pop();
found[current]=true;
for(auto itr: graph[current]){
if(found[itr]==false){
s.push(itr);
}
}
}
}
}
}
int main()
{
fin=fopen("dfs.in","r");
fout=fopen("dfs.out","w");
fscanf(fin,"%d %d",&N, &M);
for(int i=0;i<M;i++){
fscanf(fin,"%d %d", &x, &y);
graph[x].push_back(y);
graph[y].push_back(x);
}
for(int i=1;i<=N;i++){
found[i]=false;
}
dfs();
fprintf(fout,"%d",nrComp);
fclose(fin);
fclose(fout);
return 0;
}