Pagini recente » Cod sursa (job #1636581) | Cod sursa (job #2835958) | Cod sursa (job #1844260) | Cod sursa (job #2484247) | Cod sursa (job #1666072)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("dfs.in");
ofstream fout ("dfs.out");
const int nmax = 1e5+5;
const int mmax = 2e5+5;
const int bmax = 1<<19;
char buff[bmax];
int n, m, dady[nmax], rang[nmax], poz=bmax-1;
pair<int,int> v[mmax];
class scanner {
public:
inline scanner& operator >> (int &val){
while(!(buff[poz]>='0' && buff[poz]<='9'))
if(++poz==bmax) f.read(buff, bmax), poz=0;
val=0;
while(buff[poz]>='0' && buff[poz]<='9'){
val=(val<<1)+(val<<3)+buff[poz]-'0';
if(++poz==bmax) f.read(buff, bmax), poz=0;
}
return *this;
}
}fin;
int Find(int node){
while(dady[node]!=node)node=dady[node];
return node;
}
void Union(int x, int y){
if(rang[x] > rang[y]) dady[y]=x;
else dady[x]=y;
if(rang[x]==rang[y]) rang[y]++;
}
void Kruskal(){
int rx, ry, conexe, nr=0, i;
for(i=1; i<=n; i++)
dady[i]=i;
for(i=1; i<=m; i++){
rx=Find(v[i].first);
ry=Find(v[i].second);
if(rx!=ry){
nr++;
Union(rx, ry);
}
}
conexe=n-nr;
fout << conexe;
}
int main(){
ios_base::sync_with_stdio(false);
int i;
fin >> n >> m;
for(i=1; i<=m; i++)
fin >> v[i].first >> v[i].second;
Kruskal();
f.close();
fout.close();
return 0;
}