Pagini recente » Cod sursa (job #1207626) | Cod sursa (job #1335209) | Cod sursa (job #1274174) | Cod sursa (job #716965) | Cod sursa (job #468513)
Cod sursa(job #468513)
#include<fstream>
#include<stack>
#include<vector>
#include<bitset>
using namespace std;
#define nm 100001
ifstream f("dfs.in");
ofstream g("dfs.out");
int N,M,x,y,sol;
vector<int>map[nm];
bitset<nm>v;
stack<int>st;
vector<int>::iterator it;
void dfs(int i)
{ v[i]=1 , st.push(i);
while(!st.empty())
{ i=st.top(); st.pop();
for(it=map[i].begin();it!=map[i].end();it++)
if(v[*it]==0) v[*it]=1,st.push(*it);
}
}
int main()
{ f>>N>>M;
for(int i=1;i<=M;i++)
{ f>>x>>y;
map[x].push_back(y) , map[y].push_back(x);
}
for(int i=1;i<=N;i++)
{ if(v[i]==0) dfs(i) , sol++;
}
g<<sol;
f.close();
g.close();
return 0;
}