Cod sursa(job #1113637)

Utilizator dascalutudorDascalu Tudor dascalutudor Data 20 februarie 2014 19:43:24
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int Nmax=100000;
const int Mmax=1000000;
int n,m,viz[Nmax],d;
struct lista
{   int v;
    lista *urm;

};
lista *cap[Nmax],*nou;
int vecin(int ns,int i)
{   nou=cap[ns];
    while(nou)
    {   if(viz[i]==0&&i==nou->v)
        return 1;
        nou=nou->urm;
    }
    return 0;
}
void dfs(int ns)
{   int i;
    viz[ns]=1;
    for(i=1;i<=n;i++)
    {   if(vecin(ns,i)==1)
        dfs(i);

    }

}
int main()
{
    int i,a,b;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {   in>>a>>b;
        nou=new lista;
        nou->v=b;
        nou->urm=cap[a];
        cap[a]=nou;
        nou=new lista;
        nou->v=a;
        nou->urm=cap[b];
        cap[b]=nou;

    }
    for(i=1;i<=n;i++)
    {   if(viz[i]==0)
        {   d++;
            dfs(i);

        }


    }
    out<<d;

    return 0;
}