Cod sursa(job #1830916)

Utilizator nicholascantarNicholas David Cantar Gogitidze nicholascantar Data 17 decembrie 2016 11:33:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>

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