Cod sursa(job #3294097)

Utilizator DrugeaCasiandrugea DrugeaCasian Data 15 aprilie 2025 19:13:40
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
#include<algorithm>
#include<queue>
using namespace std;

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

int n, m, p, q, M[205][205],i,j,V[105],v[105];

void bfs(int k)
{
    queue<int>Q;
    Q.push(k);
    V[k] = p;
    while (!Q.empty())
    {
        k = Q.front();
        for (int i = 1; i <= n; i++)
        {
            if (M[i][k] == 1 && V[i] == 0)
            {
                V[i] = p;
                Q.push(i);
            }
        }
        Q.pop();
    }
}
int main()
{
    int i, j;
    cin >> n >> m;
    while (m--)
    {
        cin >> i >> j;
        M[i][j] = 1;
        M[j][i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        if (V[i] == 0)
        {
            ++p;
            bfs(i);
        }
    }
    cout << p << endl;
    for (int i = 1; i <= p; i++,cout<<'\n')
    {
        for (int j = 1; j <= n; ++j)
        {
            if (V[j] == i)
                cout << j << ' ';
        }
    }
}