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.

#include <bits/stdc++.h>

using namespace std;

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

int n , m , x , y , a[202][202], v[202], T[202];

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

int main()
{
    cin >> n;
    while(cin >> x >> y) a[x][y] = a[y][x] = 1 , m++;
    
    dfs(1 , 0);
    for(int i = 1 ; i <= n ; ++i)
        if(T[i] != 0) a[i][T[i]] = a[T[i]][i] = -1;///pun muchiile necesare ca sa ramana conex
        
    int diferenta = m;
    for(int i = 1 ; i < n ; ++i)
        for(int j = i + 1 ; j <= n ; ++j)
            if(a[i][j] == 1)
                if(diferenta > m / 2) a[i][j] = a[j][i] = 0 , diferenta--;///scot muchiile in plus

    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            if(a[i][j] == -1) a[i][j] = 1;

    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= n ; ++j)
            cout << a[i][j] << " ";
        cout << '\n';
    }
    return 0;
}