Cod sursa(job #3251138)

Utilizator AndreiLeusteanLeustean Andrei AndreiLeustean Data 25 octombrie 2024 09:47:53
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.27 kb
#include <iostream>
#include <string.h>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> citireGrafMatrice(string numeFisier, bool orientat, ifstream &in)
{
    int m, n;
    in >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            a[i][j] = 0;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        a[x][y] = 1;
        if (orientat == false)
            a[y][x] = 1;
    }
    return a;
}

vector<vector<int>> citireGrafListe(string numeFisier, bool orientat, ifstream &in)
{
    int m, n;
    in >> n >> m;
    vector<vector<int>> liste(n + 1);

    for (int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        liste[x].emplace_back(y);
        if (orientat == false)
            liste[y].emplace_back(x);
    }
    return liste;
}

void printMatrice(vector<vector<int>> matrice)
{
    for (int i = 1; i < matrice.size(); i++)
    {
        for (int j = 1; j < matrice[i].size(); j++)
            cout << matrice[i][j] << " ";
        cout << endl;
    }
}

void printListe(vector<vector<int>> liste)
{
    for (int i = 1; i < liste.size(); i++)
    {
        cout << i << " : ";
        for (int j = 0; j < liste[i].size(); j++)
        {
            cout << liste[i][j] << " ";
        }
        cout << endl;
    }
}

vector<vector<int>> listaLaMatrice(vector<vector<int>> liste, bool orientat)
{
    vector<vector<int>> matrice(liste.size(), vector<int>(liste.size(), 0));
    for (int i = 1; i < liste.size(); i++)
    {
        for (int j = 0; j < liste[i].size(); j++)
        {
            matrice[i][liste[i][j]] = 1;
            if (orientat == false)
                matrice[liste[i][j]][i] = 1;
        }
    }
    return matrice;
}

vector<vector<int>> matriceLaLista(vector<vector<int>> matrice, bool orientat)
{
    vector<vector<int>> liste(matrice.size());
    for (int i = 1; i < matrice.size(); i++)
    {
        for (int j = 1; j < matrice.size(); j++)
        {
            if (matrice[i][j] == 1)
                liste[i].emplace_back(j);
        }
    }
    return liste;
}

void bfs(vector<vector<int>> liste, int s, vector<int> &drum, vector<int> &tati)
{
    queue<int> coada;
    vector<bool> vizitat(liste.size(), false);
    for (int i = 0; i < liste.size(); i++)
        drum.emplace_back(-1);
    for (int i = 0; i < liste.size(); i++)
        tati.emplace_back(-1);
    coada.push(s);
    vizitat[s] = true;
    drum[s] = 0;
    tati[s] = 0;

    while (!coada.empty())
    {
        int nod = coada.front();
        // cout << nod << " ";
        coada.pop();
        for (int i = 0; i < liste[nod].size(); i++)
        {
            if (vizitat[liste[nod][i]] == false)
            {
                coada.push(liste[nod][i]);
                vizitat[liste[nod][i]] = true;
                drum[liste[nod][i]] = drum[nod] + 1;
                tati[liste[nod][i]] = nod;
            }
        }
    }
}

void dfs(vector<vector<int>> liste, int i, bool vizitat[])
{
    // cout << i << " ";
    vizitat[i] = true;
    for (int k = 0; k < liste[i].size(); k++)
        if (vizitat[liste[i][k]] == false)
            dfs(liste, liste[i][k], vizitat);
}

ifstream in("dfs.in");
ofstream out("dfs.out");
int main()
{
    int n, m;
    in >> n >> m;
    bool vizitat[n + 1];
    vector<vector<int>> liste(n + 1);

    for (int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        liste[x].emplace_back(y);
        // if (orientat == false)
        liste[y].emplace_back(x);
    }
    // printListe(liste);
    for (int i = 1; i <= n; i++)
        vizitat[i] = false;
    int nr = 0;
    for (int i = 1; i < liste.size(); i++)
    {
        if (vizitat[i] == false)
        {
            dfs(liste, i, vizitat);
            nr += 1;
            // cout << endl;
        }
    }

    out << nr;
    // bool orientare = true;
    // vector<vector<int>> liste = citireGrafListe("graf.in", orientare);
    // vector<vector<int>> matrice = citireGrafMatrice("graf.in", orientare);
    // printMatrice(matrice);
    // cout << endl;
    // printMatrice(listaLaMatrice(liste, orientare));
    // cout << endl;
    // printListe(liste);
    // cout << endl;
    // printListe(matriceLaLista(matrice, orientare));
    // cout << endl;
    // vector<int> drum;
    // vector<int> tati;
    // bfs(liste, 2, drum, tati);
    // cout << endl;
    // for (int i = 1; i < drum.size(); i++)
    //     cout << tati[i] << " ";
    // cout << endl;
    // for (int i = 1; i < drum.size(); i++)
    //     cout << drum[i] << " ";
    // int s, x;
    // cout << endl;
    // cin >> s >> x;
    // bfs(liste, s, drum, tati);
    // cout << endl;
    // if (tati[x] == -1)
    //     cout << "Nu exista drum.";
    // else
    // {
    //     vector<int> arce;
    //     arce.emplace_back(x);
    //     while (x != s)
    //     {
    //         arce.emplace_back(tati[x]);
    //         x = tati[x];
    //     }
    //     cout << endl;
    //     for (int i = arce.size() - 1; i >= 0; i--)
    //         cout << arce[i] << " ";
    // }

    return 0;
}