Cod sursa(job #1922601)

Utilizator roxanastRoxana Stiuca roxanast Data 10 martie 2017 18:00:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#define NMAX 100010
using namespace std;
struct nod{
    int vf;
    nod* urm;
};
nod* v[NMAX];
bool viz[NMAX];
int n,m,nrcomp,i;
ifstream f("dfs.in");
ofstream g("dfs.out");
void dfs(int p){
    viz[p]=true;
    for(nod* q=v[p];q;q=q->urm)
        if(!viz[q->vf])
        dfs(q->vf);
}
void form(int x,int y){
    nod* q=new nod;
    q->vf=y;
    q->urm=v[x];
    v[x]=q;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++){
        int a,b;
        f>>a>>b;
        form(a,b);
        form(b,a);
    }
    for(i=1;i<=n;i++)
        viz[i]=false;
    nrcomp=0;
    for(i=1;i<=n;i++)
    if(!viz[i]){
        ++nrcomp;
        dfs(i);
    }
    g<<nrcomp;
    return 0;
}