Pagini recente » Cod sursa (job #438845) | Cod sursa (job #2069485) | Cod sursa (job #2183659) | Cod sursa (job #502634) | Cod sursa (job #2852884)
#include <bits/stdc++.h>
using namespace std;
int n, m;
struct node
{
vector<int> vecini;
bool vizitat;
}v[100001];
void citire()
{
ifstream fin("dfs.in");
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
int a, b;
fin >> a >> b;
v[a].vecini.push_back(b);
v[b].vecini.push_back(a);
}
}
void dfs(int inceput)
{
stack<pair<int,int>> st;
st.push({inceput,0});
v[inceput].vizitat = true;
while(!st.empty())
{
auto &t = st.top();
int nod = t.first;
int i = t.second;
if(i < v[nod].vecini.size())
{
int x = v[nod].vecini[i];
t.second = i+1;
if(!v[x].vizitat)
{
v[x].vizitat = true;
st.push({x,0});
}
}
else
st.pop();
}
}
void afisare()
{
ofstream fout("dfs.out");
int cnt = 0;
for(int i = 1; i <= n; i++)
if( !v[i].vizitat )
{
cnt++;
dfs(i);
}
fout << cnt;
}
int main()
{
citire();
afisare();
return 0;
}