Cod sursa(job #2819783)

Utilizator stefandutastefandutahoria stefanduta Data 19 decembrie 2021 00:45:35
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");

bool frecvvec[NMAX];
bool frecvrand[NMAX];
int father[NMAX];
vector <int> vec[NMAX];

int main()
{
    int n, m, i, j, a, b, k = 0, gigel = 0;
    in >> n >> m;
    for (j = 1; j <= m; ++j)
    {
        in >> a >> b;
        if (father[a] == 0 && father[b] == 0)
        {
            ++k;
            father[a] = k;
            father[b] = k;
            vec[k].push_back(a);
            vec[k].push_back(b);
        }
        else if (father[a] != 0 && father[b] == 0)
        {
            father[b] = father[a];
            vec[father[b]].push_back(b);
        }
        else if (father[a] == 0 && father[b] != 0)
        {
            father[a] = father[b];
            vec[father[a]].push_back(a);
        }
        else if (father[a] != 0 && father[b] != 0)
        {
            for (i = 0; i < vec[father[b]].size(); ++i)
            {
                father[vec[father[b]][j]] = father[a];
                vec[father[a]].push_back(vec[father[b]][j]);
            }
            frecvrand[father[b]] = 1;
        }
    }
    for (j = 1; j <= k; ++j)
    {
        if (frecvrand[j] == 0)
        {
            ++gigel;
            for (i = 0; i < vec[j].size(); ++i)
            {
                frecvvec[vec[j][i]] = 1;
            }
        }
    }
    for (i = 1; i <= n; ++i)
    {
        if (frecvvec[i] == 0)
            ++gigel;
    }
    out << gigel;
    return 0;
}