Cod sursa(job #2547295)

Utilizator sipdavSipos David Oliver sipdav Data 15 februarie 2020 10:56:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

const int dim = 100001;

ifstream in("dfs.in");
ofstream out("dfs.out");

struct nod
{
    int val;
    nod* urm;
};

int n, m, nr;
bool viz[dim];
nod* muchii[dim];

void adauga(int x, int y)
{
    nod* nou = new nod;
    nou->val = y;
    nou->urm = muchii[x];
    muchii[x] = nou;
}

void dfs(int start)
{
    viz[start] = 1;
    for(nod* p = muchii[start];p != NULL;p = p->urm)
    {
        if(!viz[p->val])
            dfs(p->val);
    }
}

void read()
{
    int x, y;
    in>>n>>m;
    for(int i = 1;i <= m;i++)
    {
        in>>x>>y;
        adauga(x, y);
        adauga(y, x);
    }
}

void solve()
{
    for(int i = 1;i <= n;i++)
    {
        if(!viz[i])
        {
            nr++;
            dfs(i);
        }
    }
}

void print()
{
    out<<nr;
}

int main()
{
    read();
    solve();
    print();
    return 0;
}