Cod sursa(job #2535754)

Utilizator SimmonMuntean Simon Simmon Data 1 februarie 2020 11:10:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#define M 100005
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int i,j,k,n,m,x,y,nc,viz[M];
struct nod{
    int x;
    nod *urm;
};
nod *l[M];
nod *p;
void adauga(int i, int j){
    nod *p;
    p=new nod;
    p->x=j;
    p->urm=l[i];
    l[i]=p;

}
void df(int j){
    nod *p;
    viz[j]=1;
    p=l[j];
    while(p){
        if(viz[p->x]==0)df(p->x);
        p=p->urm;
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        l[i]=0;
    for(i=1;i<=m;i++){
        f>>x>>y;
        adauga(x,y);
        adauga(y,x);
    }
    for(i=1;i<=n;i++)
    if(viz[i]==0){nc++;df(i);}
    g<<nc;
    return 0;
}