Pagini recente » Cod sursa (job #327662) | Cod sursa (job #1081670) | Cod sursa (job #3154301) | Cod sursa (job #921964) | Cod sursa (job #2911334)
#include <fstream>
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
class array{
private:
int *p;
int n,c;
void double_size();
public:
array();
array(int x, int y);
~array();
int get_size();
void set_size(int num);
void set_size(int num, int val);
void push_back(int x);
void pop_back();
void shrink();
void operator =(array &other);
int& operator [](int x);
};
array::array(){
p=nullptr;
n=0;
c=0;
}
array::array(int x, int y){
p=new int[x];
n=x;
c=x;
}
array::~array(){
delete[] p;
}
void array::double_size(){
if(c!=0){
int *q=new int[c*2];
for(int i=0;i<n;i++){
q[i]=p[i];
}
delete[] p;
p=q;
c*=2;
}else{
c=1;
p=new int[c];
}
}
int array::get_size(){
return n;
}
void array::set_size(int x){
if(x<=c){
n=x;
}else if(x<=c*2){
double_size();
n=x;
}else{
int *q=new int[x];
for(int i=0;i<n;i++){
q[i]=p[i];
}
delete[] p;
p=q;
c=x;
n=x;
}
}
void array::set_size(int x, int y){
int oldn=n;
set_size(x);
for(int i=oldn;i<x;i++){
p[i]=y;
}
}
void array::push_back(int x){
if(n==c){
double_size();
}
p[n]=x;
n++;
}
void array::pop_back(){
n--;
}
void array::shrink(){
if(c!=n){
int *q=new int[n];
for(int i=0;i<n;i++){
q[i]=p[i];
}
delete[] p;
p=q;
c=n;
}
}
void array::operator=(array &other){
set_size(other.n);
for(int i=0;i<n;i++){
p[i]=other[i];
}
}
int& array::operator[](int x){
return p[x];
}
const int nmax=100000;
array g[nmax+1];
bool u[nmax+1];
void dfs(int x){
u[x]=1;
for(int i=0;i<g[x].get_size();i++){
int xn=g[x][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);
}
int sol=0;
for(int i=1;i<=n;i++){
if(u[i]==0){
sol++;
dfs(i);
}
}
fout<<sol<<"\n";
return 0;
}