Cod sursa(job #2229336)

Utilizator vladsirbu23Vlad Sirbu vladsirbu23 Data 6 august 2018 16:22:46
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N,M,viz[100010];
struct nod
{
    int info;
    nod *urm;
};
nod *L[400010];
void citire()
{
    nod *p;
    int i,x,y;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y;
        p=new nod;
        p->urm=L[x];
        L[x]=p;
        p->info=y;
    }
}
void dfs(int x)
{
    nod* p;
    viz[x]=1;
    p=L[x];
    while(p!=NULL)
    {
        if(viz[p->info]==0)
        {
            dfs(p->info);
        }
        p=p->urm;
    }

}
int main()
{
    int i,rez=0;
    fin>>N>>M;
    citire();
    for(i=1;i<=N;i++)
    {
        if(viz[i]==0)
        {
            dfs(i);
            rez++;
        }
    }
    fout<<rez;
}