UVa : 11550 (DEMANDING DILEMMA)


1. definition of simple graph :
a simple graph is an unweighted, undirected, no loops, no multiple edges

2. if the given graph is simple then output : Yes
otherwise : No

3. the graph representation is kind of odd
for example, lets take the first given graph
3 3
1 1 0
0 1 1
1 0 1

3 rows and each row has 3 columns
look at the first column, there are two 1’s
at row 0 and at row 2
that means, vertex 0 and 2 are connected by an edge

so, this graph indicates 3 connections :
0 – 2
0 – 1
1 – 2

4. if there are more than two 1’s in a column
then surely output : No
how could one edge connect more than two vertex!

5. another thing, if two edges connect same two vertex then output : No
because, this situation called multiple edges and its violets simple graph definition

Solution :

// http://uva.onlinejudge.org/external/115/11550.html
// Runtime : 0.016s
// Tag : simple graph, input

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

int matrix [8 + 3] [30 + 3];

int main ()
{
    int testCase;
    scanf ("%d", &testCase);

    while ( testCase-- ) {
        int n, m;
        scanf ("%d %d", &n, &m);

        for ( int i = 0; i < n; i++ ) {
            for ( int j = 0; j < m; j++ )
                scanf ("%d", &matrix [i] [j]);
        }

        bool output = true;

        for ( int i = 0; i < m; i++ ) {
            int sum = 0;
            for ( int j = 0; j < n; j++ )
                sum += matrix [j] [i];
            if ( sum != 2 ) output = false;
        }

        bool vertex [8 + 3] [8 + 3];
        memset (vertex, false, sizeof (vertex));

        if ( output ) {
            for ( int i = 0; i < m; i++ ) {
                int first, second, j = 0;
                while ( matrix [j++] [i] != 1 );
                first = j - 1;
                while ( matrix [j++] [i] != 1 );
                second = j - 1;

                if ( !vertex [first] [second] ) vertex [first] [second] = vertex [second] [first] = true;
                else output = false;
            }
        }

        if ( output ) printf ("Yes\n");
        else printf ("No\n");
    }

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

2 thoughts on “UVa : 11550 (DEMANDING DILEMMA)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s