Cod sursa(job #2194378)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 13 aprilie 2018 09:21:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#define NMAX 100000
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct node
{
    node *urm;
    int vec;
};
node *Prim[NMAX+2],*Ult[NMAX+2],*p;
int N,M,i,j,x,y,viz[NMAX+2],k=0;
void dfs(int nod)
{
    node *p=Prim[nod]->urm;
    viz[nod]=1;
    while(p!=NULL)
    {
        int vec=p->vec;
        if(!viz[vec]) dfs(vec);
        p=p->urm;
    }
}
int main()
{
    f>>N>>M;
    for(i=1;i<=N;i++)
    {
        Prim[i]= new node;
        Prim[i]->urm=NULL;
        Ult[i]=Prim[i];
    }
    for(i=1;i<=M;i++)
    {
        f>>x>>y;
        p=new node;
        p->urm=NULL;
        p->vec=y;
        Ult[x]->urm= p;
        Ult[x]=p;
        p=new node;
        p->urm=NULL;
        p->vec=x;
        Ult[y]->urm= p;
        Ult[y]=p;
    }
    for(i=1;i<=N;i++)
    {
        if(!viz[i]) {dfs(i);k++;}
    }
    g<<k;
    return 0;
}