# PBinfo #544 – Partial – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Se dă un graf neorientat conex cu n vârfuri și număr par de muchii. Să se determine un graf parțial al celui dat care să fie conex și să fie obținut prin eliminarea a jumătate din numărul de muchii.

Date de intrare
Fișierul de intrare partial.in conține pe prima linie numărul n, iar pe a următoarele linii perechi de numere i j, cu semnificația că există muchie de la i la j.

Date de ieșire
Fișierul de ieșire partial.out va conține matricea de adiacență a grafului parțial obținut, câte o linie a matricei pe o linie a fișierului, elementele fiecărei linii fiind separate prin exact un spațiu.

Restricții și precizări

1 ≤ n ≤ 200
1 ≤ i,j ≤ n
se garantează existența unui graf parțial cu proprietatea cerută

Exemplu:
partial.in

6
1 2
1 3
1 4
1 5
1 6
2 4
2 5
3 4
3 5
4 5
4 6
5 6
partial.out

0 1 0 0 0 0 
1 0 0 1 0 0 
0 0 0 1 1 0 
0 1 1 0 0 1 
0 0 1 0 0 1 
0 0 0 1 1 0 
Observații

2016, iunie 02: am adăugat un test cu o situație care nu era cuprinsă în testele anterioare.

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;
ifstream fin ("partial.in");
ofstream fout("partial.out");
int n , a[205][205], v[205], t[205];
void dfs(int k, int tata)
{
	t[k] = tata;
	v[k] = 1;
	for(int i =1 ; i <= n ; ++i)
		if(a[k][i] == 1)
			if(v[i] == 0)
				dfs(i, k);
}
int main()
{
    int i , j , m = 0;
    fin >> n;
    while(fin >> i >> j)
    {
		a[i][j] = a[j][i] = 1;
    	m ++;
    }
    dfs(1 , 0);
    for(int i = 1 ; i <= n ; ++i)
		if(t[i] != 0)
			a[i][t[i]] = a[t[i]][i] = 2;
	int k = m;
	for(int i=1 ; i < n ; ++i)
		for(int j = i + 1 ; j <= n ; ++j)
			if(a[i][j] == 1)
				if(k > m / 2)
				{
					a[i][j] = a[j][i] = 0;
					k --;
				}
	for(int i=1 ; i <= n ; ++i)
		for(int j = 1 ; j <= n ; ++j)
			if(a[i][j] == 2)
				a[i][j] = 1;
	for(int i=1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= n ; ++j)
			fout << a[i][j] << " ";
		fout << "\n";
	}
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/544)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/544/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-544/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)