Cod sursa(job #1460944)

Utilizator adrghAndrei Gheorghe adrgh Data 14 iulie 2015 13:43:56
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,viz[100005];

typedef struct Pnod{
    int x;
    Pnod *urm;
}*nod;
nod v[100005];

void adaugare(nod &dest,int val)
{
    nod p;
    p=new Pnod;
    p->x=val;
    p->urm=dest;
    dest=p;
}
void dfs(int no)
{
    nod p;
    viz[no]=1;
    for(p=v[no];p!=NULL;p=p->urm)
    {
        if(!viz[p->x])
            dfs(p->x);
    }
}
int main()
{
    f>>n>>m;
    int a,b;
    for(int i=1;i<=n;i++)
    {
        f>>a>>b;
        adaugare(v[a],b);
        adaugare(v[b],a);
    }
    int count=0;
    for(int i=1;i<=n;i++)
    {
        if(!viz[i])
        {
            count++;
            dfs(i);
        }
    }
    g<<count;
    return 0;
}