Pagini recente » Cod sursa (job #2067826) | Cod sursa (job #2914835) | Cod sursa (job #2604849) | Cod sursa (job #2621618) | Cod sursa (job #1807348)
#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;
}