Cod sursa(job #1752530)

Utilizator DaumuiEste Eu Intradevar Daumui Data 4 septembrie 2016 12:56:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");

int n,m;

int start[100002], t[400004][2];

void citeste(){
    int i,j,k=0;
    in>>n>>m;
    while(in>>i>>j){
        k++;
        t[k][0]=j;
        t[k][1]=start[i];
        start[i]=k;
        k++;
        t[k][0]=i;
        t[k][1]=start[j];
        start[j]=k;
    }
}

int s[100002],nr=0;

int df(int k){
    int p;
    //cout<<k<<" ";
    s[k]=1;
    p=start[k];
    while(p){
        if(s[t[p][0]] == 0)
            df(t[p][0]);
        p= t[p][1];
    }
}

int main()
{
    
    citeste();
    /*
    int p;
    for(int i=1;i<=n;i++){
        cout<<"Nodul "<<i<<": ";
        p=start[i];
        while(p){
            cout<<t[p][0]<<" ";
            p= t[p][1];
        }
        cout<<"\n";
    }
    */
    for(int i=1;i<=n;i++)
        if(s[i] == 0){
            df(i);
            nr++;
        }
    out<<nr;




    in.close();
    out.close();
    return 0;
}