Cerinţa

Se dă lista muchiilor unui graf neorientat. Să se determine numărul de muchii care pot fi eliminate din graf astfel încât numărul de componente conexe ale grafului să nu se modifice.

Date de intrare

Fişierul de intrare componenteconexe2.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 componenteconexe2.out va conţine pe prima linie numărul NR de muchii care pot fi eliminate.

Restricţii şi precizări

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

Exemplu

componenteconexe2.in

7
1 4
1 6
2 3
2 7
3 7
4 5
4 6
6 5

componenteconexe2.out

3

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

ifstream cin("componenteconexe1.in");
ofstream cout("componenteconexe1.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 - 1 << '\n';

    for(int i = 2 ; i <= nrc; i++)
    {
        int rez = 0;
        for(int j = 1 ; j <= n && rez == 0; j++)
            if(i == v[j]) rez = j;
        cout << 1 << " " << rez << " ";
    }
}