Pagini recente » Cod sursa (job #1138019) | Cod sursa (job #1023076) | Cod sursa (job #1280938) | Cod sursa (job #2271189) | Cod sursa (job #1593155)
#include <iostream>
#include <utility>
#include <fstream>
#include <vector>
#include <unordered_map>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int p[100003],rang[100003];
void FormeazaMutlime(int x)
{
p[x] = x;
rang[x] = 0;
}
int GasesteMultime(int x)
{
int tata =x,y;
while(p[tata] !=tata)
tata = p[tata];
while(p[x]!=x)
y = p[x], p[x] = tata, x =y;
return tata;
}
void Uneste(int x, int y)
{
if(rang[x]>rang[y])
p[y] = x;
else
p[x] = y;
if(rang[x] == rang[y])
rang[y]++;
}
void Reuneste(int x, int y)
{
Uneste(GasesteMultime(x),GasesteMultime(y));
}
void ComponenteConexe( const vector< pair< int , int > >& v)
{
for(auto p:v)
if(GasesteMultime(p.first)!= GasesteMultime(p.second))
Reuneste(p.first,p.second);
}
int main()
{
int n,m;
vector< pair< int , int > > v;
int x,y;
in >> n >> m;
for(int i = 1 ; i <= n ; i++)
FormeazaMutlime(i);
for(int i = 0 ; i < m ; i++)
in >> x >> y ,v.push_back( make_pair(x,y));
ComponenteConexe(v);
unordered_map<int,int> h;
for(int i = 1 ; i <= n ; i++)
h[GasesteMultime(i)] = 1;
out<<h.size();
return 0;
}