Cod sursa(job #2318885)

Utilizator dacianouaPapadia Mortala dacianoua Data 13 ianuarie 2019 17:21:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <string.h>
#include <fstream>
#define nmax 100000
using namespace std;
int n,m,viz[nmax+5],cnt=0;
struct nod
{
    int info;
    nod *urm;
}*v[nmax+5],*c[nmax+5],*d;
void baga(const int &x,const int &y)
{
    if(!v[x])
    {
        v[x]=new nod;
        v[x]->info=x;
        c[x]=new nod;
        c[x]->info=y;
        c[x]->urm=0;
        v[x]->urm=c[x];
    }
    else
    {
        d=new nod;
        d->info=y;
        d->urm=0;
        c[x]->urm=d;
        c[x]=d;
    }
    if(!v[y])
    {
        v[y]=new nod;
        v[y]->info=y;
        c[y]=new nod;
        c[y]->info=x;
        c[y]->urm=0;
        v[y]->urm=c[y];
    }
    else
    {
        d=new nod;
        d->info=x;
        d->urm=0;
        c[y]->urm=d;
        c[y]=d;
    }
}
void dfs(int k)
{
    viz[k]=1;
    cnt++;
    nod *e;
    e=v[k];
    while(e->urm)
    {
        e=e->urm;
        if(!viz[e->info])
        dfs(e->info);
    }
}
int main()
{
    int x,y,s=0;
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    fin>>n>>m;
    memset(v,0,sizeof(v));
    memset(c,0,sizeof(c));
    while(fin>>x>>y)
        baga(x,y);
    for(int i=1;i<=n;i++)
    {
        if(!viz[i] && v[i])
            {s++;dfs(i);}
    }
    fout<<s+n-cnt;
    return 0;
}