Cod sursa(job #2785808)

Utilizator mihneadv@yahoo.comDavid Mihnea Stefan [email protected] Data 19 octombrie 2021 16:23:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
vector<vector<int>>v;
int X, U;
vector<bool> ap;
void DFS(int nod)
{
    ap[nod] = true;
    for(int i = 0; i < v[nod].size(); i++)
    {
        if(ap[v[nod][i]] == false)
        {
            ap[v[nod][i]] = true;
            DFS(v[nod][i]);
        }
    }
}
int main()
{
    cin >> X >> U;
    v.resize(X);
    ap.resize(X);
    for(int i = 0; i < U; i++)
    {
        int V1, V2; cin >> V1 >> V2;
        v[V1 - 1].push_back(V2 - 1);
        v[V2 - 1].push_back(V1 - 1);
    }
    int cnt = false;
    for(int i = 0; i < X; i++)
    {
        if(ap[i] == false)
        {
            cnt++;
            DFS(i);
        }
    }
    cout << cnt;
    /*for(int j = 0; j < X; j++)
    {
        cout << j + 1 << " : " ;
        for(int i = 0; i < v[j].size(); i++)
        {
            cout << v[j][i] + 1 << " ";
        }
        cout << '\n';
    }*/
    return false;
}