Page 8 of 9

Re: 459 - Graph Connectivity - WA

Posted: Tue Sep 17, 2013 11:18 pm
by dumle
Ok, so my second for-loop was flawed since it only checked vectors right beside eachother.
Fixed it with a nested for-loop so it passed the test above, still WA tho :/

Code: Select all

ac

Re: 459 - Graph Connectivity - WA

Posted: Thu Sep 19, 2013 12:44 am
by brianfry713
Rewrite your code.

I solved it using DFS.

Re: 459 - Graph Connectivity - WA

Posted: Sat Sep 21, 2013 1:09 am
by brianfry713
Input:

Code: Select all

2

A

B
Output should be:

Code: Select all

1

2

Re: 459 - Graph Connectivity - WA

Posted: Wed Nov 13, 2013 5:27 am
by Skynet094
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
#define MAX 500

int parent[MAX];

int find_r(int a);
void make_set(int N);
void Union(int a, int b);
int disjoint_count(int n);



void make_set(int N)
{
for(int i=1;i<=N;i++)
parent=i;
}


void Union(int a, int b)
{

int u=find_r(a);
int v=find_r(b);

if(u==v)
return;
else
{parent[v]=u;

}

}

int find_r(int a)
{
if(parent[a]==a)
return a;
else
{
return parent[a]=find_r(parent[a]);


}

}


int disjoint_count(int n)
{


int par[MAX];

int iter=0;
int flag;

for(int i=1;i<=n;i++)
{
flag=0;
int temp=find_r(i);

for(int j=iter+1;j>=1;j--)
if(par[j]==temp)
{
flag=1;
break;
}

if(flag==0)
{
par[++iter]=temp;

}

}



return iter;


}



int main(void)
{

int testcase;
cin>>testcase;
fflush(stdin);

int lol=testcase;
char ch;
string line;
vector<string>container;

while(testcase--)
{
memset(parent,0,sizeof(parent));

getline(cin,line);
cin>>ch;
fflush(stdin);

// cout<<ch<<endl;

make_set(ch-64);

getline(cin,line);
//cout<<line<<endl;

while(!line.empty())
{
container.push_back(line);
getline(cin,line);
}

for(int i=0;i<container.size();i++)
{
Union(container[0]-64,container[1]-64);
}

int _count=disjoint_count(ch-64);

cout<<_count<<endl;
if(testcase!=1)
cout<<"\n"<<endl;


}


return 0;
}
//Can someone tell me what to change, the code gives correct output in my compiler

Re: 459 - Graph Connectivity - TLE

Posted: Wed Nov 13, 2013 10:15 am
by shariftech
Getting TLE ... I think it occurs because of ugly input ... But can not understand where is my fault ...

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#define MAX 5000

using namespace std;
int par[1000];
int flag;
int node;
void makeset (int n)
{

    for(int i=1; i<=n; i++)
        par[i] = i;
}

int find (int a)
{

    if(par[a]==a) return a;
    else
        return par[a] = find(par[a]);
}

void makeunion(int a, int b)
{

    int u = find(a);
    int v = find(b);

    if(u!=v){
            par[u] = v;
    }
}
int char2int (char c)
{

    return c-'A'+1;
}

void input()
{

    char ch[5];
    while(gets(ch)&&ch[0]){

        int ln;
        ln = strlen(ch);
        if(ln==1){
            node = char2int(ch[0]);
            makeset(node);
        }
        else{
            int a = char2int(ch[0]);
           int b = char2int(ch[1]);
            makeunion(a,b);
        }

    }
}
void free ()
{
    for(int i=0; i<=node; i++){
        par[i]=0;
    }
    node = 0;
}

int main()
{
    int n,i,j,a,b,cnt;

    scanf("%d%*c%*c",&n);
    flag = 0;

    while(n--){
        input();
        cnt = 0;
        for(i=1; i<=node; i++){
                if(par[i]==i)
                    cnt++;
        }
        if(flag==0)
            flag = 1;
        else
        cout<<endl;
        cout<<cnt;
        free();
    }



    return 0;
}

Re: 459 - Graph Connectivity - WA

Posted: Thu Nov 14, 2013 3:29 am
by brianfry713
Skynet094, don't use fflush(stdin);

Re: 459 - Graph Connectivity - WA

Posted: Thu Nov 14, 2013 3:31 am
by brianfry713
shariftech, The outputs of two consecutive cases will be separated by a blank line. Always print a newline char at the end of the last line.

uva 459

Posted: Wed Nov 20, 2013 7:38 pm
by walking_hell
thanxxxxx....got accepted

Re: uva 459

Posted: Wed Nov 20, 2013 10:00 pm
by brianfry713
Try input:

Code: Select all

1

Z
AC
AD
AE
AI
AL
AM
AN
AO
AQ
AS
AV
AW
AX
AY
BF
BH
BJ
BK
BL
BM
BN
BO
BP
BQ
BR
BU
BV
BW
BY
CE
CG
CI
CJ
CM
CP
CT
CU
CV
CY
DF
DG
DJ
DK
DL
DM
DN
DO
DQ
DV
DX
EF
EH
EK
EL
EM
EN
EO
ER
ES
ET
EU
EY
EZ
FG
FH
FI
FJ
FM
FN
FO
FP
FR
FU
FW
FY
FZ
GH
GL
GM
GP
GQ
GR
GS
GZ
HI
HJ
HK
HL
HQ
HR
HS
HV
HW
HY
IK
IM
IO
IP
IR
IU
IV
IX
IY
IZ
JK
JL
JM
JN
JR
JW
KM
KO
KP
KR
KS
KX
KY
KZ
LO
LP
LQ
LR
LY
MN
MO
MP
MR
MT
MU
MV
MX
MZ
NP
NR
NT
NV
NY
OQ
OV
OW
OX
PR
PS
PT
PV
PW
PX
PY
PZ
QR
QT
QV
QY
RT
RU
RW
RY
RZ
ST
SV
SZ
TX
TY
TZ
UW
UY
UZ
VW
WZ
XY
XZ
Your code is throwing a seg fault

Re: uva 459

Posted: Thu Nov 21, 2013 8:13 pm
by shuvokr
@raihan.sust try this input:

Code: Select all

1

E
AB

Code: Select all

so the graph is
A -> B
C
D
E
So what should be the result

Re: uva 459

Posted: Wed Mar 26, 2014 7:21 pm
by RookiE3
Please somebody help me with this code. I am getting TLE... It gives correct answers I think

Code: Select all

#include <bits/stdc++.h>
using namespace std;

int par[30];

void makeset(int n)
{
    par[n] = n;
}

int findpar(int n)
{
    if(par[n] == n)
        return n;
    else
        return (par[n] = findpar(par[n]));
}

void Union(int a, int b)
{
    int para = findpar(a);
    int parb = findpar(b);

    if(para != parb)
    {
        par[parb] = para;
    }
}

int main()
{
    freopen("in.txt", "r", stdin);

    set<int> Sets;
    int num, t;
    char largest, a, b;

    scanf("%d", &t);
    getchar();
    getchar();
    while(t--)
    {
        Sets.clear();
        num = 0;
        scanf("%c", &largest);
        if(largest == '\n')
            break;
        getchar();

        for(char i='A'; i<=largest; i++)
            makeset(i-64);

        while(true)
        {
            a = getchar();
            if(a != '\n')
                b = getchar();
            else
                break;
            Union(a-64, b-64);
            getchar();
        }
        for(char i='A'; i<=largest; i++)
        {
            Sets.insert(findpar(i-64));
        }
        printf("%d\n\n", Sets.size());
    }
    return 0;
}


Re: uva 459

Posted: Wed Mar 26, 2014 8:30 pm
by brianfry713
Don't read from a file.

Re: uva 459

Posted: Tue Apr 01, 2014 8:20 pm
by RookiE3
Please somebody help me. I am getting TLE in this problem...

Code: Select all

#include <bits/stdc++.h>
using namespace std;

int par[30];
int num;

void makeset(int n)
{
    par[n] = n;
}

int findpar(int n)
{
    if(par[n] == n)
        return n;
    else
        return (par[n] = findpar(n));
}

void Union(int a, int b)
{
    int para = findpar(a);
    int parb = findpar(b);

    if(para != parb)
    {
        par[parb] = para;
        num++;
    }
}

int main()
{
    int t;
    char largest;
    char a, b;
    scanf("%d", &t);
    getchar();
    while(t--)
    {
        num = 0;
        scanf("%c", &largest);
        getchar();
        for(char i='A'; i<=largest; i++)
            makeset(i-64);

        while(true)
        {
            a = getchar();
            if(a != '\n')
                b = getchar();
            else
                break;
            cout << a << " " << b;
            Union(a-64, b-64);
            getchar();
        }

        printf("%d\n", num);
    }
    return 0;
}

Re: uva 459

Posted: Tue Apr 01, 2014 9:28 pm
by brianfry713
Try running your code on the sample input.

Re: 459 - Graph Connectivity

Posted: Wed Oct 08, 2014 6:30 pm
by mgavin2
I'm gonna throw my code up here because I'm not exactly sure what I'm doing wrong for this problem.
I'm new to trying to solve graph problems (that weren't implicit graphs modeled as ascii maps for like floodfill problems), so I'm trying to model this problem input as an adjacency matrix... and I think I'm traversing it right.

Thanks for your code review and insights that'll help me on other graph problems :).

Code: Select all

AC

thank bfry :>