Pagini recente » Statistici Proca Victor (Vic_Civ) | Cod sursa (job #1737277) | Cod sursa (job #1830625) | Cod sursa (job #2307745) | Cod sursa (job #2069658)
#include <iostream>
#include <fstream>
#include <vector>
#define DIM 100020
#define DIM2 200020
using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
vector <vector <int> > comp(DIM2);
int n,m,nr;
int t[DIM],r[DIM];
int Find( int x)
{
int rad,elem;
rad=x;
while (t[rad]!=0)
rad=t[rad];
while (t[x]!=0)
{
elem=t[x];
t[x]=rad;
x=elem;
}
return rad;
}
void Union (int x,int y)
{
if (r[x]>r[y])
t[y]=x;
else if (r[x]<r[y])
t[x]=y;
else
{
t[x]=y;
r[y]++;
}
}
int main()
{
int x,y,rad1,rad2,i,j;
fin>>n>>m;
nr=n;
for (i=1;i<=n;i++)
comp[i].push_back(i);
while (m>0)
{
fin>>x>>y;
rad1=Find(x);
rad2=Find(y);
if (rad1!=rad2)
{
if (r[rad1]>=r[rad2])
{
for (i=0;i<comp[y].size();i++)
comp[x].push_back(comp[y][i]);
comp[y].clear();
Union(rad1,rad2);
nr--;
}
else
{
for (i=0;i<comp[x].size();i++)
comp[y].push_back(comp[x][i]);
comp[x].clear();
Union(rad1,rad2);
nr--;
}
}
m--;
}
fout<<nr<<"\n";
/*for (i=1;i<=n;i++)
if (comp[i].empty()==0)
{
for (j=0;j<comp[i].size();j++)
fout<<comp[i][j]<<" ";
fout<<"\n";
}
*/
fin.close();
fout.close();
return 0;
}