Cod sursa(job #1848780)

Utilizator NaritaAndreiNarita Andrei NaritaAndrei Data 16 ianuarie 2017 17:30:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int nr,i,x,y,m,n,start[100001],t[2][2*100001],d[100001];
void citire()
{ int k=0;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>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 fill(int x)
{
   int  k=start[x]; d[x]=1;
    while(k!=0)
    {
        if(d[t[0][k]]==0)
        {
            fill(t[0][k]);
        }
        k=t[1][k];
    }
}
void parcurgere()
{
    for(i=1;i<=n;i++)
    {
        if(d[i]==0)
            {nr++;fill(i);}
    }
    g<<nr;
}
int main()
{
    citire();
    parcurgere();
    return 0;
}