uva 793 - Network Connections

Network Connections

Bob, who is a network administrator, supervises a network of computers. He is keeping a log connections between the computers in the network. Each connection is bi-directional. Two computers are interconnected if they are directly connected or if they are interconnected with the same computer. Occasionally, Bob has to decide, quickly, whether two given computers are connected, directly or indirectly, according to the log information.


Write a program which based on information input from a text file counts the number of successful and the number of unsuccessful answers to the questions of the kind :


is computer_i interconnected with computer_j ?

Input and Output 

The first line of the input contains the number of dataset, and it's followed by a blank line. Each dataset is defined as follows:

1.

The number of computers in the network (a strictly positive integer);

2.

A list of pairs of the form:

(a)

c computer_i computer_j, where computer_i and computer_j are integers from 1 to. A pair of this form shows that computer_i and computer_j get interconnected.

(b)

q computer_i computer_j, where computer_i and computer_j are integers from 1 to. A pair of this form stands for the question: is computer_i interconnectedwith computer_j?

There's a blank line between datasets.
Each pair is on a separate line. Pairs can appear in any order, regardless of their type. The log is updated after each pair of type (a) and each pair of type (b) is processed according to the current network configuration.


For example, the input file illustrated in the sample below corresponds to a network of 10 computers and 7 pairs. There are N1 successfully answered questions and N2 unsuccessfully answered questions. The program prints these two numbers to the standard output on the same line, in the order: successful answers, unsuccessful answers, as shown in the sample output. Print a blank line between datasets.

Sample Input 

1

10
c 1 5
c 2 7
q 7 1
c 3 9
q 9 6
c 2 5
q 7 5

Sample Input 

1,2

---

Miguel Revilla
2001-01-05

union-set 

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int N;
int *par;
int find(int a){
    if(par[a]==a)return a;
    int c=a;
    while(par[a]!=a)a=par[a];
    return par[c]=a;
}
void merge(int to,int from){
    int a=find(to),b=find(from);
    par[b]=a;
}
int main(){
    int a,b,c,c1,c2;
    char nds[100];
    bool ll=0;
    scanf("%d",&a);
    rep(i,a){
        c1=c2=0;
        scanf("%d ",&N);
        par=(int *)malloc(N*sizeof(int));
        rep(i,N)par[i]=i;
        if(DBG)printf("N %d\n",N);
        while(fgets(nds,100,stdin)){
            if(nds[0]=='\n')break;
            if(nds[0]=='c'){
                sscanf(&nds[1],"%d%d",&b,&c),c--,b--;
                if(find(b)!=find(c))merge(b,c);
            }
            else if(nds[0]=='q'){
                sscanf(&nds[1],"%d%d",&b,&c),c--,b--;
                if(find(b)!=find(c))c2++;
                else c1++;
            }
        }
        if(ll)printf("\n");ll=1;
        printf("%d,%d\n",c1,c2);
    }
}

uva 459 - Graph Connectivity

Graph Connectivity

Consider a graph G formed from a large number of nodes connected by edges. G is said to be connected if a path can be found in 0 or more steps between any pair of nodes in G. For example, the graph below is not connected because there is no path from A to C.



This graph contains, however, a number of subgraphs that are connected, one for each of the following sets of nodes: {A}, {B}, {C}, {D}, {E}, {A,B}, {B,D}, {C,E}, {A,B,D}
A connected subgraph is maximal if there are no nodes and edges in the original graph that could be added to the subgraph and still leave it connected. There are two maximal connected subgraphs above, one associated with the nodes {A, B, D} and the other with the nodes {C, E}.
Write a program to determine the number of maximal connected subgraphs of a given graph.

Input and Output

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The first line of each input set contains a single uppercase alphabetic character. This character represents the largest node name in the graph. Each successive line contains a pair of uppercase alphabetic characters denoting an edge in the graph. The sample input section contains a possible input set for the graph pictured above.
Input is terminated by a blank line.
For each test case, the output the number of maximal connected subgraphs. The outputs of two consecutive cases will be separated by a blank line.

Sample Input

1

E
AB
CE
DB
EC

Sample Output

2

union-find 

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<set>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int N;
int par[30];
set<int>st;
int find(int a){
    if(par[a]==a)return a;
    int c=a;
    while(par[a]!=a)a=par[a];
    return par[c]=a;
}
void merge(int to,int from){
    int a=find(to),b=find(from);
    par[b]=a;
}
int main(){
    int a,b,c;
    string s;
    char nds[10];
    bool ll=0;
    scanf("%d\n",&a);
    rep(i,a){
        rep(i,30)par[i]=i;st.clear();
        fgets(nds,10,stdin),nds[strlen(nds)-1]='\0',s=nds;
        N=s[0]-'A'+1;
        if(DBG)printf("N %d\n",N);
        while(fgets(nds,10,stdin)){
            if(nds[0]=='\n')break;
            b=nds[0]-'A',c=nds[1]-'A';
            if(find(b)!=find(c)){merge(b,c);}
        }
        rep(i,N) if(!st.count(find(i)))st.insert(find(i));
        if(ll)printf("\n");ll=1;
        printf("%d\n",st.size());
    }
}