459 – Graph Connectivity UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=400

Graphs, graph traversal, dfs, connected components.

How I did it

• I read the number of cases.
• I read the number of vertices.(Max 26 vertices)
• I read the edges until I found an empty line. and set the union of the graph.
• Traverse all the not visited vertexs and call dfs(node not visited yet). Increment the number of connected component in every call to dfs.
• Print the number of connected components.

Hints

• The maximum number of nodes is 26. (From A to Z).
• The graph always will be numered from 0 to 26   0<=nodes<27
• I play with the ASCII value for get the node value. i.e ‘A’ – 65 = 0, ‘B’ – 65 = 1, ‘C’ – 65 = 2…. and so on.
• Print a blank line between cases. The last case does not need the blank line.

Code

#include <iostream>
#include <cstdio>
#include <vector>
#define  DFS_WHITE -1
#define  DFS_BLACK 1
using namespace std;
typedef vector<int> vi;

vector<vi> graph;
vi dfs_num;

void readGraph()
{
    string edge;
    int node1, node2;
    getline(cin, edge);

    while(getline(cin,edge))
    {
        if(edge.size() == 0)
           break;
        node1 = edge[0] - 65;
        node2 = edge[1] - 65;
        graph[node1].push_back(node2);
        graph[node2].push_back(node1);
    }
}

void print()
{
    for(int x=0; x<graph.size(); x++)
    {cout<<"Nodo : "<<x<<endl;
        for(int y=0; y<graph[x].size(); y++)
            cout<<graph[x][y]<<" ";
        cout<<endl;
    }
}

void dfs(int node)
{
    dfs_num[node] = DFS_BLACK;
    for(int c=0; c<graph[node].size(); c++)
        if(dfs_num[graph[node][c]] == DFS_WHITE)
          dfs(graph[node][c]);
}

int main()
{
string nodes;
int casos, CC, flag=0;
scanf("%d", &casos);
for(int x=0; x<casos; x++)
{
    cin>>nodes;
    graph.assign(nodes[0] - 64, vi());
    dfs_num.assign(nodes[0] - 64, DFS_WHITE);
    readGraph();
    //print();
    CC = 0;
    for(int z=0; z<dfs_num.size(); z++)
    {
        if(dfs_num[z] == DFS_WHITE)
        {
            dfs(z);
            CC++;
        }
    }
    if(flag == 0)
       flag++;
    else
        printf("\n");
    printf("%d\n", CC);
}
return 0;
}