Pagini recente » Cod sursa (job #2937385) | Cod sursa (job #740295) | Cod sursa (job #1492018) | Cod sursa (job #356143) | Cod sursa (job #2176182)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,nrcomp;
list <int> adj[100100];
bool viz[100100];
void dfs(int v)
{
int st[100100];
int vf=1;
st[1]=v;
viz[v]=1;
while(vf)
{
int nc=st[vf];
list <int> :: iterator i;
i=adj[nc].begin();
while(i!=adj[nc].end() and viz[*i])
++i;
if(i!=adj[nc].end())
{
int u=*i;
st[++vf]=u;
viz[u]=1;
}
else st[vf--]=0;
}
}
int main()
{f>>n>>m;
for(int i=1;i<=m;++i)
{
int a,b;
f>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1;i<=n;++i)
if(!viz[i])
{
nrcomp++;
dfs(i);
}
g<<nrcomp;
return 0;
}