Cod sursa(job #1831000)

Utilizator stefantagaTaga Stefan stefantaga Data 17 decembrie 2016 12:12:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <stack>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
stack <int> s;
struct nod
{
    int info;
    nod*urm;
}*v[100001];
int viz[100001];
void adaugare(nod*&prim,int x)
{
    nod*nou;
    nou=new nod;
    nou->urm=NULL;
    nou->info=x;

    if (prim==NULL)
    {
        prim=nou;
    }
    else
    {
        nou->urm=prim;
        prim=nou;
    }
}
void dfs (int i)
{

    viz[i]=1;

    nod*p;

    {
        for (p=v[i];p;p=p->urm)
        {
            if (viz[p->info]==0)
            {
                viz[p->info]=1;

                dfs(p->info);
            }
        }
    }
}
int main()
{
    int n,m,nrc=0,i,x,y;
    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]==0)
        {
            nrc++;
            dfs(i);
        }
    }
    g<<nrc;
    return 0;
}