Pagini recente » Cod sursa (job #1262775) | Cod sursa (job #1700082) | Cod sursa (job #2803793) | Cod sursa (job #2081211) | Cod sursa (job #2397015)
#include <bits/stdc++.h>
#define pb push_back
#define NMAX 100005
using namespace std;
struct nod{
vector<int> adj;
};
vector<nod> v;
int n,m,x,y;
bitset<NMAX> viz;
void dfs(int root)
{
stack<int> s;
int nod,w;
bool ok=1;
s.push(root);
viz[root]=1;
while (!s.empty())
{
nod = s.top();
ok=0;
for (int i=0;i<v[nod].adj.size();i++)
{
w=v[nod].adj[i];
if (!viz[w])
{
ok=1;
s.push(w);
viz[w]=1;
break;
}
}
if (!ok) s.pop();
}
}
void comp()
{
int k=0;
for (int i=1;i<=n;i++)
{
if (!viz[i])
{
dfs(i);
k++;
}
}
printf("%d", k);
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d %d", &n, &m);
v.resize(n+2);
for (int i=0;i<m;i++)
{
scanf("%d %d", &x, &y);
v[x].adj.pb(y);
v[y].adj.pb(x);
}
comp();
fclose(stdin);
fclose(stdout);
return 0;
}