Pagini recente » Cod sursa (job #1568210) | Cod sursa (job #360749) | Cod sursa (job #1201837) | Cod sursa (job #2211021) | Cod sursa (job #1462900)
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
vector<int> a[NMAX];
int rang[NMAX],uniune[NMAX],n,m,x,y,nrc,ac,b;
void create_union()
{
for(int i=1;i<=n;i++)
{
uniune[i]=i;
rang[i]=0;
}
}
void unite_union(int r1,int r2)
{
if(rang[r1]>rang[r2])
uniune[r2]=r1;
else
uniune[r1]=r2;
if(rang[r1]==rang[r2]) rang[r2]++;
}
int find_union(int x)
{
int r,y;
// cout << 1;
for(r=x; uniune[r]!=r; r = uniune[r]);
for(; x!=uniune[x]; )
{
y = uniune[x];
uniune[x]=r;
x=y;
}
//cout << 2;
return r;
}
int main()
{
ifstream in("dfs.in");
ofstream out("dfs.out");
in >> n >> m;
create_union();
for(int i=0;i<m;i++)
{
in >> x >> y;
// a[x].push_back(y);
// a[y].push_back(x);
if(find_union(x)!=find_union(y))
unite_union(find_union(x),find_union(y));
}
/*
for(int i=1;i<=n;i++)
{
ac = find_union(i);
for(int j=0;j<a[i].size();j++)
{
b = find_union(a[i][j]);
if(ac!=b)
unite_union(ac,b);
}
}
*/
for(int i=1;i<=n;i++)
if(uniune[i]==i){
nrc++;
//cout << uniune[i] << endl;
}
out << nrc;
return 0;
}