Pagini recente » Cod sursa (job #2299371) | Cod sursa (job #831039) | Cod sursa (job #2560417) | Cod sursa (job #1621594) | Cod sursa (job #671715)
Cod sursa(job #671715)
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
#define file_in "dfs.in"
#define file_out "dfs.out"
#define nmax 101000
stack<int> St;
vector<int> G[nmax];
int viz[nmax];
int N,M,a,b,i,ans;
void dfs(int nod){
int X;
St.push(nod); //bag nodul in stiva
while(!St.empty()){//stiva nu e goala
X=St.top();
St.pop();
viz[X]=1;
for (vector<int> :: iterator it=G[X].begin();it!=G[X].end();++it)
if (!viz[*it]){
viz[*it]=1;
St.push(*it);//il bag in stiva
}
}
}
int main(){
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d %d", &N, &M);
while(M--){
scanf("%d %d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
ans=0;
for (i=1;i<=N;++i)
if (!viz[i]){
ans++;
dfs(i);
}
printf("%d\n", ans);
return 0;
}