Cod sursa(job #2528297)

Utilizator CarlaDianaCarla Diana CarlaDiana Data 21 ianuarie 2020 18:53:41
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
struct nod {int info;nod *urm;};
nod *lis[100010],*q;
int n,a,b,k,v[100010],c[100010],ci,cs,m,nr;
void addnod(int a, int b)
{
    q=new nod;
    q->urm=lis[a];
    q->info=b;
    lis[a]=q;
}

void DFS(int n)
{
    nod *q;
    v[n]=1;
    q=lis[n];
    while(q!=NULL)
    {
        ///fout<<q->info<<" ";
         if(v[q->info]==0)
         {
             DFS(q->info);
         }
         q=q->urm;
    }
}

int main()
{
    fin>>n>>m;
    for(;m;m--)
    {
        fin>>a>>b;
        addnod(a,b);///in lista lui a pe b
    }
    for(int i=1;i<=n;i++)
    {
        if(v[i]==0)
        {
            DFS(i);
            nr++;
        }
    }
    fout<<nr;
    return 0;
}