#438

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 <iostream>
#include <fstream>
using namespace std;

ifstream fin("componenteconexe.in");
ofstream fout("componenteconexe.out");

int n , a[105][105];
int x[105], // coada pentru parcurgerea in latime
    v[105]; // vector caracteristic care precizeaza daca un varf a fost sau nu vizitat


void bf(int varf, int nrc)
{
    int st, dr;
    st = dr = 1;
    v[varf] = nrc;
    x[1] = varf;
    while(st <= dr)
    {
        int k = x[st];
        for(int i = 1; i <= n ; ++i)
            if(v[i] == 0 && a[k][i] == 1)
            {
                dr ++;
                v[i] = nrc;
                x[dr] = i;
            }
        st ++;
    }
}

int main()
{
    int i , j;
    fin >> n;
    while(fin >> i >> j)
    {
        a[i][j] = a[j][i] = 1;
    }

    int nrc = 0;
    for(int i=1; i <= n ;++i)
        if(v[i] == 0 )
        {
            nrc ++;
            bf(i , nrc);
        }
    fout << nrc << endl;
    for(int i=1 ; i<= nrc ; ++i)
    {
        for(int j = 1; j<= n ;++j)
            if(v[j] == i)
                fout << j << " ";
        fout << endl;
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

ifstream f("componenteconexe.in");
ofstream g("componenteconexe.out");

int v[105],n,a[105][105],vec[105],nr1=0;
void dfs(int nod)
{
    v[nod]=1;
    vec[++nr1]=nod;
    for(int k=1;k<=n;k++)
        if(a[nod][k]==1 && v[k]==0)
        dfs(k);
}
int main()
{
    int m,x,y,nr=0;
    f>>n;
        while(f>>x>>y)
        a[x][y]=a[y][x]=1;
    for(int i=1;i<=n;i++)
    {
        if(v[i]==0)
        {
            dfs(i);
            nr++;
        }
    }
    g<<nr<<endl;
    for(int i=1;i<=n;i++)
        v[i]=0;
      for(int i=1;i<=n;i++)
    {
        nr1=0;
        if(v[i]==0)
        {
            dfs(i);
            sort(vec+1,vec+nr1+1);
        for(int j=1;j<=nr1;j++)
            g<<vec[j]<<" ";
        g<<endl;
        }

    }
}