Pagini recente » Cod sursa (job #2748940) | Cod sursa (job #3157883) | Cod sursa (job #2999097) | Cod sursa (job #3150925) | Cod sursa (job #1678743)
#include <fstream>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
typedef struct nod{
int data;
nod* next;
}* graf;
graf a[1000100];
int n,m,p,b[1001],x,y;
int viz[1000010];
int c[101],u=1;
void add(int y,int x){
if (!a[y]){
a[y]=new nod;
a[y]->data=x;
a[y]->next=0;
}
else {
nod*c=new nod;
c->data=x;
c->next=a[y];
a[y]=c;
}
}
void dfs(int x){
viz[x]=1;
for(graf p=a[x];p!=NULL;p=p->next){
if(!viz[p->data]){
dfs(p->data);}
}
}
void bhs(int i){
nod* c1=a[i];
while(c1){
if (!viz[c1->data]) {
viz[c1->data]=1;
u++;
c[u]=c1->data;
}
c1=c1->next;
}
if (i<u) bhs(i+1);
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>x>>y;
add(y,x);
add(x,y);
}
/*for(int i=1;i<=p;i++)cin>>b[i];
for(int i=1;i<=p;i++){
if(!viz[b[i]])dfs(b[i]);
}
int k=0;
for(int i=1;i<=n;i++){if(!viz[i])k++;}
cout<<k<<"\n";
for(int i=1;i<=n;i++){
if(!viz[i])cout<<i<<"\n";
}
*/
int k=0;
// viz[1000010]={0};
//viz[1]=1;
u=1;
c[1]=1;
//bhs(1);
for(int j=1;j<=n;j++){
if (!viz[j]){
k++;
dfs(j);
}
}
cout <<k<<endl;
return 0;
}