Cod sursa(job #1801244)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 8 noiembrie 2016 19:52:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
# include <fstream>
# define DIM 100010
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct List{
    int val;
    List *next;
};
List *first[DIM],*last[DIM];
int Marcat[DIM],n,m,i,x,y,sol;
void push_back(int x,int y){
    if(first[x]==NULL){
        first[x]=new List;
        first[x]->val=y;
        first[x]->next=NULL;
        last[x]=first[x];
        return;
    }
    List *p;
    p=new List;
    p->val=y;
    p->next=NULL;
    last[x]->next=p;
    last[x]=p;
    return;
}
void dfs(int nc){
    List *p;
    p=first[nc];
    Marcat[nc]=1;
    while(p!=NULL){
        int nv=p->val;
        if(!Marcat[nv])
            dfs(nv);
        p=p->next;
    }
}
int main () {
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        push_back(x,y);
        push_back(y,x);
    }
    for(i=1;i<=n;i++)
        if(!Marcat[i]){
            sol++;
            dfs(i);
        }
    fout<<sol<<"\n";
    return 0;
}