Cod sursa(job #1830955)

Utilizator ioanalexandraIoan Alexandra ioanalexandra Data 17 decembrie 2016 11:47:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;
ifstream f ("dfs.in");
ofstream g ("dfs.out");
int n,m,i,viz[100001],x,y,k;
struct nod
{
    int inf;
    nod*urm;
}*v[100001];
void adaugare(nod *&prim, int x)
{
    nod*nou;
    nou=new nod;
    nou->inf=x;
    nou->urm=prim;
    if(prim==NULL)
        prim=nou;
    else
    {
        nou->urm=prim;
        prim=nou;
    }
}
void dfs(int x)
{
    viz[x]=1;
    nod*j;
    for(j=v[x]; j!=NULL; j=j->urm)
        if(viz[j->inf]==0)
            dfs(j->inf);
}
int main()
{
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y;
        adaugare(v[x],y);
        adaugare(v[y],x);
    }
    for(i=1; i<=n; i++)
    {
        if(!viz[i])
        {
            dfs(i);
            k++;
        }
    }
    g<<k;
    return 0;
}