Pagini recente » Cod sursa (job #1794528) | Cod sursa (job #1616659) | Cod sursa (job #1032829) | Cod sursa (job #1563898) | Cod sursa (job #1801244)
# include <fstream>
# define DIM 100010
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct List{
int val;
List *next;
};
List *first[DIM],*last[DIM];
int Marcat[DIM],n,m,i,x,y,sol;
void push_back(int x,int y){
if(first[x]==NULL){
first[x]=new List;
first[x]->val=y;
first[x]->next=NULL;
last[x]=first[x];
return;
}
List *p;
p=new List;
p->val=y;
p->next=NULL;
last[x]->next=p;
last[x]=p;
return;
}
void dfs(int nc){
List *p;
p=first[nc];
Marcat[nc]=1;
while(p!=NULL){
int nv=p->val;
if(!Marcat[nv])
dfs(nv);
p=p->next;
}
}
int main () {
fin>>n>>m;
for(i=1;i<=m;i++){
fin>>x>>y;
push_back(x,y);
push_back(y,x);
}
for(i=1;i<=n;i++)
if(!Marcat[i]){
sol++;
dfs(i);
}
fout<<sol<<"\n";
return 0;
}