Pagini recente » Cod sursa (job #97690) | Cod sursa (job #1198295) | Cod sursa (job #2605013) | Cod sursa (job #2413274) | Cod sursa (job #2418701)
#include <iostream>
#include <stack>
#include <vector>
FILE * fin= fopen("dfs.in","r");
FILE * fout= fopen("dfs.out","w");
std::stack<int> s;
std::vector<int> v[100050];
int t[100050];
bool vis[100050];
int n,m;
int countt;
int main()
{
fscanf(fin,"%d %d",&n,&m);
for(int i=0;i<m;i++)
{
int j,k;
fscanf(fin,"%d %d",&j,&k);
v[j].push_back(k);
v[k].push_back(j);
}
for(int i=1;i<=n;i++)
{
if(vis[i])continue;
countt++;
vis[i]=true;
s.push(i);
while(!s.empty())
{
int tp = s.top();
int j=t[tp];
for(;j<v[tp].size();j++)
{
t[tp]=j+1;
int elem = v[tp][j];
if(!vis[elem])
{
vis[elem]=true;
s.push(elem);
break;
}
}
if(j==v[tp].size()) s.pop();
}
}
fprintf(fout,"%d",countt);
}