Cod sursa(job #1923642)

Utilizator qqqpppqqq ppp qqqppp Data 11 martie 2017 20:15:14
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#define MAX_N 100000
using namespace std;
struct list{
        int inf;
        list* urm;
} *g[MAX_N+1];
int n,m;
int used[MAX_N+1];
 
 
void iofile(void){
        freopen(FIN,"rt",stdin);
        freopen(FOUT,"wt",stdout);
        scanf("%d%d",&n,&m);
        int x,y;
        list* q;
        for (int i=1;i<=m;i++){
                scanf("%d%d",&x,&y);
                q=new list;q->inf=y;q->urm=g[x];g[x]=q;
                q=new list;q->inf=x;q->urm=g[y];g[y]=q;
        }
        fclose(stdin);
}
 
 
 
void dfs(int nod){
        for (list* q=g[nod];q;q=q->urm){
                if (!used[q->inf]){
                        used[q->inf]=1;
                        dfs(q->inf);
                }
        }
}
 
void solve(void){
        int nrcomp=0;
        for (int i=1;i<=n;i++){
                if (!used[i]){
                        used[i]=1;
                        nrcomp++;
                        dfs(i);
                }
        }
        printf("%d\n",nrcomp);
        fclose(stdout);
}
 
int main(void){
        iofile();
        solve();
        return 0;
}