## 459 - Graph Connectivity

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 459 - Graph Connectivity

The outputs of two consecutive cases will be separated by a blank line. Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

### Re: 459 - Graph Connectivity - WA

Yeah... I was trying that... it's commented out in the main function because I was still getting WA
Then I saw:
brianfry713 wrote: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.
and changed it and got WA

*edit*
actually, maybe the last stupid line of input isn't a blank line of \n and has spaces.

*edit2*
It fails for test case:

Code: Select all

``````1

A
``````
*edit3*
freaking convoluted input with C/C++

Code: Select all

``````bool getInput()
{
//get input
char a, b;
char line[50];
scanf("%c%c", &a, &b);
debug(a, TAB);
FOR(i, 'A', a+1)
AdjMat[i][i] = 1;
while (fgets(line, 50, stdin), (line[0] != ' ' && line[0] != '\n') &&
!feof(stdin))
{
debug(line, TAB);
sscanf(line, "%c%c ", &a, &b);
debug(a, TAB); debug(b, endl);
AdjMat[a][b] = 1;
AdjMat[b][a] = 1;
//if (feof(stdin)) break;
}
return true;
}
``````

Thanks, I got AC
all that matters is AC

ehsanulbigboss
New poster
Posts: 32
Joined: Tue Jul 22, 2014 1:17 am

### Re: 459 - Graph Connectivity

Why Getting WA???

Code: Select all

``Got AC! Check the newline instructions``

Rika71
New poster
Posts: 11
Joined: Sat Apr 26, 2014 9:42 pm

### Re: 459 - Graph Connectivity

cant get ac , please help, thanks in advance.

using dfs :

Code: Select all

``````#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(i=0;i<n;i++)
#define rep1(i,n) for(i=1;i<=n;i++)
#define pb push_back
#define siz 1000
char s[10];
char vis[siz];
vector <long> g[siz];
void dfs(long src)
{
if(vis[src]) return;
if(g[src].size()==0)
{
vis[src]=2;
return;
}
vis[src]=1;
long i,z;
rep(i,g[src].size())
{
z=g[src][i];
dfs(z);
}
vis[src]=2;
}
int main()
{
map < char,long > ma;
long x,y,z,i,j,t,cas,ass,save,cnt,u,v;
char ch1,ch2;
scanf("%ld%*c",&t);
rep1(cas,t)
{
ass=0;
memset(vis,0,sizeof(vis));

scanf("%s%*c",s);
ch1=s[0];
ma[ch1]=++ass;
while(1)
{
if(gets(s)==NULL) break;
if(!strcmp(s,"")) break;
sscanf(s,"%c%c",&ch1,&ch2);
//if(ma.find(ch1)==ma.end()) ma[ch1]=++ass;
//if(ma.find(ch2)==ma.end()) ma[ch2]=++ass;
if(!ma[ch1]) ma[ch1]=++ass;
if(!ma[ch2]) ma[ch2]=++ass;
i=ma[ch1],j=ma[ch2];
g[i].pb(j);
g[j].pb(i);
}
cnt=0;
rep1(i,ass)
{
if(vis[i]==0) dfs(i);
else cnt++;
}

printf("%ld\n",cnt);
if(cas!=t) puts("");
rep1(i,ass)
{
g[i].clear();
}
ma.clear();
}

return 0;
}

``````

using disjoint set:

Code: Select all

``````#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(i=0;i<n;i++)
#define rep1(i,n) for(i=1;i<=n;i++)
#define siz 10000
char s[10];
long par[siz];

long find_root(long i)
{
return (par[i]==i) ? i : (par[i]=find_root(par[i]));
}
int main()
{
long x,y,z,i,j,t,cas,ass,save,cnt,u,v;
char ch1,ch2;
scanf("%ld%*c",&t);
rep1(cas,t)
{
ass=0;
memset(par,0,sizeof(par));
map < char,long > ma;
scanf("%s%*c",s);
ch1=s[0];
ma[ch1]=++ass;
par[ass]=ass;
while(1)
{
if(gets(s)==NULL) break;
if(!strcmp(s,"")) break;
sscanf(s,"%c%c",&ch1,&ch2);
//if(ma.find(ch1)==ma.end()) ma[ch1]=++ass;
//if(ma.find(ch2)==ma.end()) ma[ch2]=++ass;
if(!ma[ch1]) ma[ch1]=++ass;
if(!ma[ch2]) ma[ch2]=++ass;
i=ma[ch1],j=ma[ch2];
if(!par[i]) par[i]=i;
if(!par[j]) par[j]=j;

u=find_root(i),v=find_root(j);
if(u!=v) par[v]=u;
}
//printf("as  %ld\n",ass);
rep1(i,ass) find_root(i);
sort(par+1,par+ass+1);
cnt=save=0;
rep1(i,ass)
{
//printf("%ld ",par[i]);
if(par[i]!=save)
{
cnt++;
save=par[i];
}
}
printf("%ld\n",cnt);
if(cas!=t) puts("");
}

return 0;
}

``````
both produce wa

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 459 - Graph Connectivity

Yout dfs version doesn't match sample I/O. Check disjoint version for input in this thread.
brianfry713 wrote:Input:

Code: Select all

``````2

A

B``````
Output should be:

Code: Select all

``````1

2``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

messiNayan
New poster
Posts: 7
Joined: Thu Feb 20, 2014 7:07 pm

### Runtime Error .Help me

Code: Select all

``````#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
bool flag[26];
int par[26];
int findRef(int x);
void findUnion(char a, char b);
int main(void)
{
int i,j,t;
char s[3];
scanf("%d",&t);
gets(s);
gets(s);
while (t--)
{
for (i = 0; i < 26; i++)
par[i] = i;
memset(flag,false,sizeof(flag));
int limit = (getchar() - 65);
gets(s);
while (strlen(gets(s)))
findUnion(s[0], s[1]);

for (j = 0; j <= limit; j++)
flag[findRef(j)] = true;

int cnt = 0;
for (j = 0; j <= limit; j++)
{
if (flag[j])
cnt++;
}
printf("%d\n\n",cnt);

}
return 0;
}
void findUnion(char a, char b)
{
int p = a - 65;
int q = b - 65;
int u = findRef(p);
int v = findRef(q);
if (u != v)
par[u] = v;
}

int findRef(int x)
{
if (x == par[x])
return x;
return (par[x] = findRef(par[x]));
}``````
Last edited by brianfry713 on Fri Jan 23, 2015 9:40 pm, edited 1 time in total.
Reason: Added code blocks

MDSP777
New poster
Posts: 1
Joined: Sat Jan 24, 2015 5:00 pm

### Re: 459 - Graph Connectivity

Help please! Can't get AC, I've tried every test input on this forum, and passed them, so I dunno what's wrong. I used dfs/floodfill to solve it.
Note: I remove the /**/ for the sc.hasNext() whenever I make a submission

Code: Select all

``````AC
``````
Last edited by MDSP777 on Mon Mar 27, 2017 5:56 pm, edited 2 times in total.

techyvish
New poster
Posts: 9
Joined: Wed Nov 19, 2014 2:32 am

### Re: 459 - Graph Connectivity

Hi, I tried all inputs in forum. I'm getting correct answers locally, but getting WA with online judge. Please help !!
here is the code.

Code: Select all

``````
#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <fstream>
#include <string>
#include <list>

using namespace std;

#define fin cin

namespace UVA459 {

class Graph{

list<int> *adj;
int V;
int *visited;
int connectedComp = 0;

public:

Graph (int v)
{
V = v;
adj = new list<int>[V];
visited = new int[V];
memset(visited, 0, sizeof(int) * V);
}

void addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}

int connectedComponents()
{
for ( int i = 0 ; i < V ; i++ )
{
if ( !visited[i])
{
connectedComp ++;
dfs(i);
}
}
return connectedComp;
}

void  dfs(int v)
{
visited[v] = true;
for (auto i = adj[v].begin() ; i != adj[v].end() ; ++i )
{
if ( !visited[*i] )
{
dfs(*i);
}
}
}

};
}

int main()
{
//fstream fin("uva459.txt");

int tc;
fin >> tc;

char c;
fin >> c ;
int N = c-65;

while ( tc -- ) {
UVA459::Graph g(N+1);
string str;
while (fin >> str ) {
if ( str.length() == 1)
{
N = str[0]-65;
break;
}
int node1 = str[0] - 65;
int node2 = str[1] - 65;

if ( node1 <= N && node2 <= N )
g.addEdge(node1, node2);

}

int cc = g.connectedComponents();
cout << cc ;
if ( tc != 0 )
{
cout << endl ;
}

}

return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 459 - Graph Connectivity

messiNayan, The outputs of two consecutive cases will be separated by a blank line, don't print an extra blank line at the end.
MDSP777, use class Main, post the code you'd actually submit.
techyvish, always print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

techyvish
New poster
Posts: 9
Joined: Wed Nov 19, 2014 2:32 am

### Re: 459 - Graph Connectivity

thanks brianfry713, got AC, It expects new line between each line.

mr.wa
New poster
Posts: 1
Joined: Sun Sep 13, 2015 7:12 pm

### Re: 459 - Graph Connectivity

I coded in Java. I have tried for almost every possible inputs and it shows correct output. But I am getting Run Time Error continuously. Can anybody help?

Code: Select all

``````
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Graph g ;
List<String> alphabets;

Scanner sc = new Scanner(System.in);

int tc = sc.nextInt();
sc.nextLine();

for (int i = 0; i < tc; i++) {

if(i>0)
System.out.print("\n");

g = new Graph();
alphabets = new ArrayList<String>();

String limit = sc.next();
Character ch = limit.charAt(0);

for(Character c = 'A' ; c <= ch ; c++)
alphabets.add(c.toString());

for(String s: alphabets) {
g.addNode(s);
}

sc.nextLine();

String s;

while ((s = sc.nextLine()) != null) {

if(s.trim().equals(""))
break;

String next[] = s.trim().split("[ ]+");

if(next.length == 1) {

Character node1 = next[0].charAt(0);
Character node2 = next[0].charAt(1);

g.addEdge(node1.toString(), node2.toString());

}

else
g.addEdge(next[0], next[1]);

}

g.depthFirstSearch("A");
System.out.println(g.subgraph);
}

}

}

class Graph {

private Map<String, Node> nodes;
int time;
int subgraph;

public Graph() {
this.nodes = new HashMap<String, Node>();
}

void initializeNodes(){

for (String v : nodes.keySet()) {

Node node = nodes.get(v);
node.setColor(Node.Color.WHITE);
node.setDiscoveryTime(Integer.MAX_VALUE);
node.setFinishTime(Integer.MAX_VALUE);
node.setParent(null);

nodes.put(v, node);
}

}

public void addNode (String node){
nodes.put(node, new Node(node));
}

public void addEdge (String node1, String node2) {

if(!nodes.containsKey(node1))
addNode(node1);

if(!nodes.containsKey(node2))
addNode(node2);

List<String> head = nodes.get(node1).getAdjacentNodes();

if(head == null)
head = new ArrayList<String>();
head.add(node2);
nodes.get(node1).setAdjacentNodes(head);

List<String> tail = nodes.get(node2).getAdjacentNodes();

if(tail == null)
tail = new ArrayList<String>();
tail.add(node1);
nodes.get(node2).setAdjacentNodes(tail);

}

void depthFirstSearch (String source) {

time = 0;
subgraph =1;

initializeNodes();

/******* DFS With Source ********/

Node snode = nodes.get(source);
DFS_Visit(snode);

// This part is for the disconnected tree from source

for (String v : nodes.keySet()) {

Node node = nodes.get(v);

if(node.getColor() == Node.Color.WHITE) {
subgraph++;
DFS_Visit(node);
}
}
}

void DFS_Visit(Node unode) {

time++;

unode.setColor(Node.Color.GRAY);
unode.setDiscoveryTime(time);

if(unode.getAdjacentNodes() != null) {

for(String v: unode.getAdjacentNodes()) {

Node vnode = nodes.get(v);

if(vnode.getColor() == Node.Color.WHITE) {
vnode.setParent(unode.getId());

DFS_Visit(vnode);
}

//                else
//                    return true;     // Cycle exists
}
}

time++;

unode.setColor(Node.Color.BLACK);
unode.setFinishTime(time);
}

void printDiscoverAndFinishTime() {

for (String v : nodes.keySet()) {

Node node = nodes.get(v);

System.out.print(node.getId());
System.out.print(" " +node.getDiscoveryTime());
System.out.println(" " +node.getFinishTime());
}
}

void getShortestPath(String source, String des) {

List<String> list = new ArrayList<String>();

Node currentNode = nodes.get(des);
list.add(des);

while(!currentNode.getId().equals(source)) {

if(currentNode.getParent()== null) {
list.clear();
break;
}

currentNode = nodes.get(currentNode.getParent());

list.add(currentNode.getId());

}

int size = list.size();

if(size == 0)
System.out.println("No route");
else {

for (int i = size; i > 1 ; i--) {
System.out.println(list.get(i-1)+" "+list.get(i-2));
}
}
//        System.out.println("");
}

}

class Node {

public static enum Color {WHITE, GRAY, BLACK};

private final String id;
private String parent = null;
private List<String> adjacentNodes;

private Color color = Color.WHITE;

private int discoveryTime = Integer.MAX_VALUE;
private int finishTime = Integer.MAX_VALUE;

public Node(String id) {
this.id = id;
}

public String getId() {
return this.id;
}

public String getParent() {
return this.parent;
}

public void setParent(String parent) {
this.parent = parent;
}

public int getDiscoveryTime(){
return this.discoveryTime;
}

public void setDiscoveryTime(int discoveryTime) {
this.discoveryTime = discoveryTime;
}

public int getFinishTime(){
return this.finishTime;
}

public void setFinishTime(int finishTime) {
this.finishTime = finishTime;
}

public Color getColor(){
return this.color;
}

public void setColor(Color color){
this.color = color;
}

public List<String> getAdjacentNodes(){
return this.adjacentNodes;
}

public void setAdjacentNodes(List<String> vertices) {
this.adjacentNodes = vertices;
}

}

``````

carofe82
New poster
Posts: 3
Joined: Thu Oct 22, 2015 7:11 am

### Re: 459 - Graph Connectivity

mr.wa,
I think you need to put the Node and the Graph class inside the Main class

Code: Select all

``````public class Main{
...

static class Graph{
...
}

static class Node{
...
}

}
``````

punter
New poster
Posts: 2
Joined: Thu Aug 04, 2016 8:16 am

### Re: 459 - Graph Connectivity

I am getting Runtime Error for my Python code. Can someone point out the mistakes in my code? TIA.

Code: Select all

``````def dfs(u, G, visited):
visited[u] = True
for v in G[u]:
if(not visited[v]): dfs(v, G, visited)

def main():
G = []
visited = [False] * 30
for i in range(30): G.append([])

tc = int(input())
n = input() #dump

for cn in range(1, tc+1):
n = ord(input()) - 64
assert n < 30
for i in range(n):
G[i].clear()
visited[i] = False

while 1:
edge = input()
if edge == '': break
i = ord(edge[0]) - 65
j = ord(edge[1]) - 65
assert i<30 and j<30
G[i].append(j)
G[j].append(i)

ans = 0
for i in range(n):
if not visited[i]:
dfs(i, G, visited)
ans += 1

if(cn > 1): print('')
print(ans)

if __name__ == '__main__':
main()
``````