Cod sursa(job #2212712)

Utilizator georgitTreista Georgiana georgit Data 14 iunie 2018 17:20:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <vector>

using namespace std;

vector <int> vecini[100001];
bool fr[100001];
void Fill(int nod)
{
    for(int i=0;i<vecini[nod].size();i++)
    {
        if(fr[vecini[nod][i]]==0)
        {
            fr[vecini[nod][i]]=1;
            Fill(vecini[nod][i]);
        }
    }
}
int main()
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    int n,m;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
       int a,b;
       f>>a>>b;
       vecini[a].push_back(b);
       vecini[b].push_back(a);
    }
    int comp=0;
    for(int i=1;i<=n;i++)
    {

        if(fr[i]==0)
        {
            comp++;
            Fill(i);
        }

    }
    g<<comp;

    return 0;
}