Cod sursa(job #2667909)

Utilizator marian222200Dimofte Marian marian222200 Data 4 noiembrie 2020 01:53:05
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#define N 100001
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nod{
    nod *urm;
    int info;
};
nod *l[N];
int viz[N];
int n,m;
void citire(){
    int i,x,y;
    nod *p;
    fin>>n>>m;
    for(i=1;i<=n;i++){
        fin>>x>>y;
        p=new nod;
        p->info=y;
        p->urm=l[x];
        l[x]=p;
        p=new nod;
        p->info=x;
        p->urm=l[y];
        l[y]=p;
    }
}
void dfs(int s,int nr){
    viz[s]=nr;
    nod *p;
    for(p=l[s];p!=NULL;p=p->urm)if(viz[p->info]==0)dfs(p->info,nr);
}
void colorare(){
    int i,col=0;
    for(i=1;i<=n;i++)
        if(viz[i]==0)dfs(i,++col);
    fout<<col;
}
int main(){
    citire();
    colorare();
    return 0;
}