Cerinţa

Se dă lista muchiilor unui graf neorientat. Să se afișeze componentele conexe ale acestui graf.

Date de intrare

Fişierul de intrare componenteconexe.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire componenteconexe.out va conţine pe prima linie numărul de componente conexe nrc. Fiecare dintre următoarele nrc linii va conține în ordine crescătoare, separate printr-un spațiu, vârfurile din componenta conexă curentă.

Ordinea de afișare a componentelor conexe va fi cea crescătoare a vârfului cu eticheta minimă din fiecare componentă.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• în fișierul de intrare muchiile se pot repeta

Exemplu

componenteconexe.in

5
1 4 
3 5
2 4

componenteconexe.out

2
1 2 4
3 5

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

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

int n , m , x , y , a[101][101] , v[101] , nrc;

void dfs(int x , int val)
{
    v[x] = val;
    for(int i = 1 ; i <= n ; i++)
        if(!v[i] && a[x][i] == 1) 
        {
            dfs(i , val);
            v[i] = val;
        }
}

int main()
{
    cin >> n;
    while(cin >> x >> y) 
    {
        a[x][y] = a[y][x] = 1;
        m++;
    }

    for(int i = 1 ; i <= n ; i++)
        if(v[i] == 0) dfs(i , nrc + 1) , nrc++;

    cout << nrc << '\n';

    for(int i = 1 ; i <= nrc ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
            if(i == v[j]) cout << j << " ";
        cout << '\n';
    }
}