Pagini recente » Cod sursa (job #2403635) | valentin | Cod sursa (job #2734936)
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct vint{
int *v=nullptr;
int capacity=0, size=0;
void push_back(int x);
void pop_back();
void resize(int x);
void resize(int x, int y);
void shrink_to_fit();
};
void vint::push_back(int x){
if(v==nullptr){
v=new int[1];
v[0]=x;
size++;
capacity=1;
}else if(capacity==size){
int *v2=new int[capacity*2];
for(int i=0;i<size;i++){
v2[i]=v[i];
}
delete[] v;
v=v2;
capacity*=2;
v[size]=x;
size++;
}else{
v[size]=x;
size++;
}
}
void vint::pop_back(){
if(size>0){
size--;
}
}
void vint::resize(int x){
if(capacity<x){
capacity=x;
int *v2=new int[capacity];
for(int i=0;i<size;i++){
v2[i]=v[i];
}
delete[] v;
v=v2;
}
size=x;
}
void vint::resize(int x, int y){
if(capacity<x){
capacity=x;
int *v2=new int[capacity];
for(int i=0;i<size;i++){
v2[i]=v[i];
}
delete[] v;
v=v2;
}
for(int i=size;i<x;i++){
v[i]=y;
}
size=x;
}
void vint::shrink_to_fit(){
capacity=size;
int *v2=new int[size];
for(int i=0;i<size;i++){
v2[i]=v[i];
}
delete[] v;
v=v2;
}
const int nmax=100000;
vint g[nmax+1];
bool u[nmax+1];
void dfs(int x){
u[x]=1;
for(int i=0;i<g[x].size;i++){
int xn=g[x].v[i];
if(u[xn]==0){
dfs(xn);
}
}
}
int main(){
int n,m;
fin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
fin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;i++){
g[i].shrink_to_fit();
}
int sol=0;
for(int i=1;i<=n;i++){
if(u[i]==0){
sol++;
dfs(i);
}
}
fout<<sol<<"\n";
return 0;
}