Question

Se da un graf prin n noduri si m muchii.Sa se afiseze cea mai lunga componenta conexa.Inceputul stiu sa-l fac,citirea,DFS/BFS,daca este comp conexa sau nu....dar nu stiu cum sa o afisez pe cea mai lunga.

Answer 1

#include <bits/stdc++.h>
using namespace std;

const int NMax = 1005;

int n, m, sol;
vector<int> Graf[NMax];
bitset<NMax> Viz;
queue<int> Q;

int BFS(int sursa)
{
    int nrNoduri = 1;

    Viz[sursa] = true;
    Q.push(sursa);

    while(!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        for(const auto & vecin : Graf[nod])
            if(!Viz[vecin]) {
                Q.push(vecin);
                Viz[vecin] = true;
                nrNoduri++;
            }
    }

    return nrNoduri;
}

int main()
{
    cin >> n >> m;
    for(int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        Graf[x].push_back(y);
        Graf[y].push_back(x);
    }

    for(int i = 1; i <= n; i++)
        if(!Viz[i])
            sol = max(sol, BFS(i));
    cout << sol << '\n';
    return 0;
}