Cod sursa(job #1807348)

Utilizator mariusmagureanmagurean marius mariusmagurean Data 16 noiembrie 2016 13:49:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.14 kb
#include <fstream>
#include<vector>
#define dim 100020
#define dim2 200020
using namespace std;

vector <vector<int> > comp(dim2);
int n,m,nr;
int t[dim],r[dim];

int find(int x)
{
    //caut radacina subarborelui in care se gaseste x si aplic compresia caii pentru toate nodurile incepand de la x
    //din acel arbore, nodurile situate sub x nu vor fi compresate!
    int rad=x;
    while(t[rad]!=0)
        rad=t[rad];
    //compresia caii
    int y;
    while(t[x]!=0)
    {
        y=t[x];
        t[x]=rad;
        x=y;
    }
    return rad;
}

void uniune(int rad1,int rad2)
{
    //aplica uniunea a doi arbori, dupa rang, adica arborele cu rang mai mic se uneste la arborele cu rang mai mare,
    //adica radacina arborelui mai mic va avea ascendent radacina arborelui mai mare
    //evident rangul arborelui mai mare nu creste prin uniune
    //daca rangul este egal inseamna ca rangul noului arbore va fi cu 1 mai mult
    //vom uni practic subarborii care au radacina rad1, respectiv rad2
    if(r[rad1]>r[rad2])
        t[rad2]=rad1;
    else
        if(r[rad1]<r[rad2])
            t[rad1]=rad2;
        else
        {
            t[rad2]=rad1;
            r[rad1]++;
        }
}
int main()
{
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    int x,y,rad1,rad2,i,j;
    fin>>n>>m;
    //pp numarul de compo conexe ca fiind n
    nr=n;
    for(i=1;i<=n;i++)
        comp[i].push_back(i);

    while(m>0)
    {
        fin>>x>>y;
        //apelez find ptr amandoua extremitatile, daca au aceeasi radacina fac parte din aceeasi comp conexa
        //daca au radacini diferite adaug in componenta conexa a radacinei
        //elimin componenta conexa a nodului care se adauga la alta componenta prin stergerea nodului
        //ma folosesc de rang pentru a sti la ce componenta conexa adaug
        rad1=find(x);
        rad2=find(y);
        //daca am egalitate nu adaug nimic, nodurile sunt deja incluse
        if(rad1!=rad2)
        {
            if(r[rad1]>=r[rad2])
            {
                //toata lista lui y se va adauga componentei lui x
                //unim
                //golim lista lui y
                //scadem nr
                for(i=0;i<comp[y].size();i++)
                    comp[rad1].push_back(comp[y][i]);
                comp[y].clear();
                uniune(rad1, rad2);
                nr--;
            }
            else
            {
                //x se va adauga la y
                //unim
                //glim lista lui x
                //scadem nr
                for(i=0;i<comp[x].size();i++)
                    comp[rad2].push_back(comp[x][i]);
                comp[x].clear();
                uniune(rad1, rad2);
                nr--;
            }
        }
        m--;
    }
    //nr ne va indica nr de componente conexe
    //parcurgem comp si daca linia nu este vida, listam nodurile componentei
    fout<<nr<<"\n";
    /*for(i=1;i<=n;i++)
        if(comp[i].empty()==false)
        {
            for(j=0;j<comp[i].size();j++)
                fout<<comp[i][j]<<" ";
            fout<<"\n";
        }
    */
    return 0;
}