Cod sursa(job #1678743)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 7 aprilie 2016 15:17:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#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;   
}