Cod sursa(job #1774132)

Utilizator raduzxstefanescu radu raduzx Data 8 octombrie 2016 16:50:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>

using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct nod
{
    int val;
    nod *urm;
};
typedef nod *pnod;
pnod v[100002];
pnod p;
int n;
int ad(int x,int y)
{
    p=v[x]->urm;
    while(p)
    {
        if(p->val==y)
            return 0;
        p=p->urm;
    }
    p=new nod;
    p->urm=v[x]->urm;
    p->val=y;
    v[x]->urm=p;
    return 1;
}
bool a[100002];
int t[100002],k,s,i;
void dfs(int varf)
{
    k=s=1;
    t[1]=varf;
    a[varf]=1;
    while(k<=s)
    {
        p=v[t[k]]->urm;
        while(p)
        {
            if(a[p->val]==0)
            {
                a[p->val]=1;
                s+=1;
                t[s]=p->val;
            }
            p=p->urm;
        }
        k+=1;
    }
}
int main()
{
    int j,x,y,m;
    f>>n;
    f>>m;
    for(i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        ad(x,y);
        ad(y,x);
    }
    int nr=0;
    for(i=1;i<=n;i++)
    {
       if(a[i]==0)
       {
           nr+=1;
           dfs(i);
       }
    }
    g<<nr;
    return 0;
}