Pagini recente » Cod sursa (job #3316672) | Cod sursa (job #981491) | Cod sursa (job #3351787) | Borderou de evaluare (job #1499947) | Cod sursa (job #3306476)
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;
string filename = "dfs";
ifstream in(filename + ".in");
ofstream out(filename + ".out");
vector<int> r, parent;
int findParent(int node)
{
if(parent[node] == node)
return node;
return parent[node] = findParent(parent[node]);
}
int conex;
void unite(int a, int b)
{
int parA = findParent(a);
int parB = findParent(b);
if(parA==parB)
return;
if(r[parA] < r[parB])
parent[parA] = parB;
else if (r[parB] < r[parA])
parent[parB] = parA;
else
parent[parB] = parA,
r[parA]++;
conex--;
}
int n, m;
int main()
{
in>>n>>m;
r.resize(n+1,0);
parent.resize(n+1);
for(int i = 0; i<=n;i++)
parent[i]=i;
conex=n;
int a,b;
for(int i = 1; i<=m ;i++)
{
in>>a>>b;
unite(a,b);
}
out<<conex;
return 0;
}