Pagini recente » Cod sursa (job #1971623) | Cod sursa (job #1829835) | Cod sursa (job #300985) | Cod sursa (job #267889) | Cod sursa (job #841859)
Cod sursa(job #841859)
#include <stdio.h>
#include <stdlib.h>
////////////// LIST ///////////////////
typedef struct tagNode
{
int vecin;
struct tagNode *next;
}Node;
typedef struct tagList
{
Node* start;
}List;
void initList(List *list)
{
list->start = NULL;
}
void addList(List *list, int vecin)
{
Node *new = malloc(sizeof(Node));
new->next = list->start;
new->vecin = vecin;
list->start = new;
}
////////////////////////////////////////
#define MAXN 100001
int M,N;
int visited[MAXN];
int componente;
List vecini[MAXN];
int dfs(int node)
{
visited[node] = 1;
Node *q = vecini[node].start;
while( q != NULL){
int vecin = q->vecin;
if( !visited[vecin] ){
dfs(vecin);
}
q=q->next;
}
}
int main(int argc, char* argv[])
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d %d",&N,&M);
int i,a,b;
for(i=1;i<=N;i++){
initList(&vecini[i]);
}
for(i=0;i<M;i++){
scanf("%d %d",&a,&b);
addList(&vecini[a],b);
addList(&vecini[b],a);
}
for(i=1;i<=N;i++){
if( !visited[i] ){
componente++;
dfs(i);
}
}
printf("%d",componente);
return 0;
}