Cod sursa(job #2229333)

Utilizator vladsirbu23Vlad Sirbu vladsirbu23 Data 6 august 2018 16:17:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N,M,Start[100010],T[2][400010],q[100010],viz[100010];
void citire()
{
    int i,x,y,k;
    k=0;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y;
        k++;
        T[0][k]=y;
        T[1][k]=Start[x];
        Start[x]=k;
        k++;
        T[0][k]=x;
        T[1][k]=Start[y];
        Start[y]=k;
    }
}
void dfs(int nod)
{
    int p;
    viz[nod]=1;
    p=Start[nod];
    while(p)
    {
        if(viz[T[0][p]]==0)
        {
            dfs(T[0][p]);
        }
        p=T[1][p];
    }

}
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;
}