# UVA Graph Problem Solution,uva-255, uva-315,uva-821,uva-10600

UVA Graph Problem Solution  are more difficult in UVa  Problem set but Graph problem are more important because most of the graph  problem are related  to real life problem. Graph problems are,Graph Traversal,Maximum Flow,Minimum Spanning Tree,Single-Source Shortest Paths ,All-Pairs Shortest Paths, Special Graph (Directed Acyclic Graph) & Special Graphs(Others). Here are the list of some uva Graph Problem Solution,uva-255, uva-315,uva-821,uva-10600

# UVa: 259(Software Allocation)

#include<stdio.h>
#include<string.h>

char str[100];

struct ss {
int Job[30];
int ind;
}com[12];

int F[30], T, Count[30], A[12];

void Reset() {
int i;
for(i = 0; i<10; i++) {
F[i] = com[i].ind = Count[i] = 0;
}
for(i; i<30; i++)
F[i] = Count[i] = 0;
}

void Set() {
int i, j, k, m;
k = str[0]-'A';
m = str[1] - '0';
F[k] += m;
T += m;
for(i = 3; str[i] != ';'; i++) {
j = str[i] - '0';
com[j].Job[com[j].ind++] = k;
}
}
void Print() {
int i, j;
for(i = 1; i<11; i++) {
j = A[i];
if(j == 28) printf("_");
else printf("%c",j+'A');
}
printf("\n");
}

int BackTrak(int n, int level, int total, int cm) {
int i, j, m, k;
A[level] = cm;
if(level == 10 ) {
if( T == total) {
Print();
return 1;
}
return 0;
}
Count[cm] ++;
for(i = n+1; i<10; i++) {
for(j = 0; j<com[i].ind; j++) {
m = com[i].Job[j];
k = total;
if(m != 28) k = total+1;
if(Count[m] < F[m] || m == 28)
if(BackTrak(i,level+1,k,m)) return 1;
}
}
Count[cm] --;
return 0;
}
void Cal() {
int i, j;
for(i = 0; i<10; i++)
com[i].Job[com[i].ind++] = 28;
if(T>10){
printf("!\n");
return;
}
j = BackTrak(-1,0,0,29);
if(!j) printf("!\n");
}
void main() {
int i;
//freopen("c:\\h.in","r",stdin);
while(gets(str)) {
T = 0;
Set();
while(gets(str)) {
for(i = 0; str[i]; i++) {
if(str[i] == '\n') {
str[i] = NULL;
break;
}
}
if(strlen(str) == 0) break;
Set();
}
Cal();
Reset();
}
}

# UVa: 315(NetWork)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAXN 102

int p[MAXN], rank[MAXN];
char L[MAXN][MAXN];

int N, cp;

void Ini() {
int i;
for( i = 1; i<= N; i++){
p[i] = i;
rank[i] = 0;
}
}

int Find(int x) {
if(x != p[x])
p[x] = Find(p[x]);
return p[x];
}

void Link(int x, int y) {
if(rank[x] > rank[y])
p[y] = x;
else {
p[x] = y;
if(rank[x] == rank[y])
rank[y]++;
}
}
char input[1000], *p;
int n, m;
while(gets(input)) {
p = strtok(input," ");
n = atoi(p);
if(!n) break;
while(p) {
p = strtok(NULL," ");
if(p) {
m = atoi(p);
L[n][m] = L[m][n] = 1;
}
}
}
}
void SolvedCase() {
int i, j, k, c = 0;
int x, y, t;
for(i = 1; i<= N; i++) {
Ini();
t = N-1;
for(j = 1; j<N; j++) {
if(j == i) continue;
for(k = j+1; k<= N; k++) {
if(k == i) continue;
if(L[j][k] == 1) {
x = Find(j);
y = Find(k);
if(x != y){
t--;
}
}
}
}
if(t-1 >0 ) c++;
}
printf("%d\n",c);
}

void main() {
char input[1000];
int i, j;
while(gets(input)){
sscanf(input,"%d",&N);
if(!N) break;
Ini();
cp = N-1;
SolvedCase();
for( i = 1; i<= N; i++)
for( j = i+1; j<=N; j++)
L[i][j] = L[j][i] = 0;
}
}

# UVa: 821(Page Hopping)

#include<stdio.h>

#define MAX 105
#define MIN(a, b) (a>b?b:a)
#define INF 214748

int A[MAX], F[MAX];
int maxN;

void Ini() {
int i, j;
for(i = 1; i<= 100; i++) {
for(j = i+1; j<= 100; j++)
F[i] = 0;
}
}

void Floyd() {
int i, j, k;
int p, q, r;
for(k = 0; k<maxN; k++) {
p = A[k];
for(i = 0; i< maxN; i++) {
q = A[i];
for(j = 0; j< maxN; j++) {
r = A[j];
}
}
}
}

void Cal(int kase){
int i, j, p, q;
double sum = 0, total;
Floyd();
for(i = 0; i<maxN; i++) {
p = A[i];
for(j = i+1; j< maxN; j++){
q = A[j];
}
}
total = maxN*(maxN-1);
printf("Case %d: average length between pages = %.3lf clicks\n",kase,sum/total);
}

void main() {
int a, b, kase = 1;
while(1) {
maxN = 0;
scanf("%d%d",&a,&b);
if(!a && !b) break;
Ini();
if(!F[a]) { A[maxN++] = a; F[a] = 1; }
if(!F[b]) { A[maxN++] = b; F[b] = 1; }
while(1) {
scanf("%d%d",&a,&b);
if(!a && !b) break;
if(!F[a]) { A[maxN++] = a; F[a] = 1; }
if(!F[b]) { A[maxN++] = b; F[b] = 1; }
}
Cal(kase++);
}
}

# UVa: 10600(ACM Contest and Blackout)

#include<stdio.h>
#include<stdlib.h>

#define MAXN 102
#define MAXE 5055

struct ss {
int u, v;
int weight;
}E[MAXE],MST[MAXE];

int P[MAXN], rank[MAXN];
int N, M;

int com(const void *a, const void *b) {
ss *x = (ss *)a;
ss *y = (ss *)b;
return x->weight - y->weight;
}

int Find(int n) {
if(n != P[n])
P[n] = Find(P[n]);
return P[n];
}

void Link(int x, int y) {
if(rank[x]>rank[y])
P[y] = x;
else {
P[x] = y;
if(rank[x] == rank[y])
rank[y] ++;
}
}

void MakeSet() {
int i;
for(i = 0; i<N; i++) {
rank[i] = 0;
P[i] = i;
}
}

int mSt(int p, int c) {
int sum = 0, i, x, y;
int mstLen = 0;
for(i = 0; i<M && mstLen<N-1; i++) {
if((E[i].u == MST[p].u && E[i].v == MST[p].v)) continue;
x = Find(E[i].u);
y = Find(E[i].v);

if(x != y){
sum += E[i].weight;
if(sum > c) return -1;
mstLen++;
}
}
if(mstLen==N-1)
return sum;
return -1;
}

void Cal() {
int i, mstLen = 0, x, y, f = 0;
int Best_1 = 0, Best_2 = 21474836;
MakeSet();
qsort(E,M,sizeof(ss),com);
for(i = 0; i<M && mstLen<N-1; i++) {
x = Find(E[i].u);
y = Find(E[i].v);
if(x != y){
MST[mstLen++] = E[i];
Best_1 += E[i].weight;
}
}
printf("%d",Best_1);
for(i = 0; i<mstLen; i++) {
MakeSet();
x = mSt(i,Best_2);
if(x != -1 && x<Best_2 ){
f = 1;
Best_2 = x;
}
}
if(f) printf(" %d\n",Best_2);
else printf(" %d\n",Best_1);

}

void main() {
int kase, i;
//freopen("c:\\in.txt","r",stdin);
scanf("%d",&kase);
while(kase--) {
scanf("%d%d",&N,&M);
for(i = 0; i<M; i++){
scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].weight);
E[i].u--;
E[i].v--;
}
Cal();
}
}