459 - Graph Connectivity

[brianfry713]

The outputs of two consecutive cases will be separated by a blank line. Don't print an extra blank line at the end.

[mgavin2]

Yeah... I was trying that... it's commented out in the main function because I was still getting WA
Then I saw:

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

[ehsanulbigboss]

Why Getting WA???

Code: Select all

Got AC! Check the newline instructions

[Rika71]

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]

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

Input:

Code: Select all

2

A

B

Output should be:

Code: Select all

1

2

[messiNayan]

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]));
}

[MDSP777]

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

[techyvish]

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]

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.

[techyvish]

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

[mr.wa]

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]

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]

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()

[Nakar81]

Input terminated by EOF!!!! Not by blank line! When I change it I got AC!

The answer to my problem was this.
If you use Scanner in Java, check with sc.hasNextLine() before sc.nextLine(), otherwise you will get runtime error.