Cod sursa(job #1690503)

Utilizator emity03Vrabie Vladislav emity03 Data 15 aprilie 2016 10:43:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>

using namespace std;

ifstream cin("dfs.in");
ofstream cout("dfs.out");

typedef struct nod
{
       int nr;
       nod *next;
}* graf;
graf a[100005];

int N,M,x,y,k=1;
bool viz[100005];

void add(graf &p, int n)
{
    graf z=new nod;
    z->nr=n;
    z->next=p;
    p=z; 
     
}     

void dfs(int n)
{
     graf p=new nod;
     viz[n]++;
     for(p=a[n]; p; p=p->next)
                 if(!viz[p->nr]) dfs(p->nr);
     
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>N>>M;
    
    for(int i=1; i<=M; ++i)
    {
     cin>>x>>y;
     add(a[x],y);
     add(a[y],x);
    }
    dfs(1);
    for(int i=2; i<=N; ++i)
     if(!viz[i])dfs(i), k++;
    cout<<k;
return 0;
}