11504 - Dominos

[MarioYC]

Hi. I've been trying to solve this problem, but when I try the test cases in Waterloo's web page http://plg1.cs.uwaterloo.ca/~acm00/080927/data/D.6.dat, my code gives an answer only for the two firt cases.

First, I find all the connected components and then I see if a connected component affects another one, then I only take the connected components which aren't affected by any other connceceted component.

Code: Select all

#include<iostream>
#include<vector>

using namespace std;

vector< vector<int> > L1;
vector< vector<int> > L2;
vector<int> v;
bool visited[100000];
int component[100000];
int num_components;
bool in_component[100000];

void dfs1(int start){
    visited[start]=true;
    
    for(int i=0;i<L1[start].size();i++)
        if(!visited[L1[start][i]])
            dfs1(L1[start][i]);
    
    v.push_back(start);
}

void dfs2(int start){
    visited[start]=true;
    component[start]=num_components;
    
    for(int i=0;i<L2[start].size();i++)
        if(!visited[L2[start][i]])
            dfs2(L2[start][i]);
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    
    int T,n,m,a,b,cont;
    
    scanf("%d",&T);
    
    for(int caso=0;caso<T;caso++){
        scanf("%d %d",&n,&m);
        
        L1.clear();
        L1.resize(n);
        L2.clear();
        L2.resize(n);
        
        for(int i=0;i<m;i++){
            scanf("%d %d",&a,&b);
            
            L1[a-1].push_back(b-1);
            L2[b-1].push_back(a-1);
        }
        
        fill(visited,visited+n,false);
        v.clear();
        
        for(int i=0;i<n;i++){
            if(!visited[i]){
                dfs1(i);
            }
        }
        
        fill(visited,visited+n,false);
        
        num_components=0;
        
        for(int i=v.size()-1;i>=0;i--){
            if(!visited[v[i]]){
                dfs2(v[i]);
                num_components++;
            }
        }
        
        fill(in_component,in_component+num_components,false);
        
        for(int i=0;i<n;i++)
            for(int j=0;j<L1[i].size();j++)
                if(component[i]!=component[L1[i][j]])
                    in_component[component[L1[i][j]]]=true;
        
        cont=0;
        
        for(int i=0;i<num_components;i++)
            if(!in_component[i]) cont++;
        
        cout<<cont<<endl;
    }
    
    return 0;
}

[gba356]

Hi, I have been given constant WAs for the problem.

First of all, I consider the dominos a directed graph.

And I tried to approach the problem by DFS-ing through the nodes with no in-edge, and then DFS the nodes that are not visited , and then print the numbers of dominos knocked down by hand.

I passed the official test cases University of Waterloo provides:

http://plg1.cs.uwaterloo.ca/~acm00/080927/data/D.6.dat
http://plg1.cs.uwaterloo.ca/~acm00/080927/data/D.6.diff

But the judge keeps giving me WA, and the program halts in 0.400 second. I don't know where's the problem, is my algorithm

correct?

P.S. I chose adjacency lists with dynamic memory allocation as my graph data structure, maybe I have some small error on handling the dynamic memory allocation. I'll post my code if needed

Best regards

[andmej]

It may fail in some cases. For example, if you have the following graph:

3 nodes and these directed edges: <1, 2> <2, 1> and <3, 2>

If you start the DFS at node 1 you will visit nodes 1 and 2. Then you will also knockdown tile 3, with total score 2 (Tiles 1 and 3). But the best solution is to just knock tile 3.

First you have to reduce the graph to its directed components graph, which is acyclic and works with your algorithm.

[gba356]

It may fail in some cases. For example, if you have the following graph:

3 nodes and these directed edges: <1, 2> <2, 1> and <3, 2>

If you start the DFS at node 1 you will visit nodes 1 and 2. Then you will also knockdown tile 3, with total score 2 (Tiles 1 and 3). But the best solution is to just knock tile 3.

First you have to reduce the graph to its directed components graph, which is acyclic and works with your algorithm.

Hi, first of all, thank you for your reply.

For the instance above you mentioned, my algorithm will DFS from vertex 3 first, which is the only vertex without in-edges. No error occurs when I test on my computer as desired.

Here's my algorithm, I wonder if my greedy is correct:

1. Find the vertices without in-edges.
2. DFS by taking the vertices with indegree zero as start points; mark the vertices "visited" so as not to be visited second time.
3. DFS through the remains, for cycle detection.
4. Output the answer.

And the following is my commented code, I chose adjacency lists as my graph data structure:

Code: Select all

#include<iostream>
#define N 100001
using namespace std;

struct Node{                        /* adjacency list */
    int now;
    Node* next;
} root[N];                          

    bool visited[N],indegree[N];    /* if indegree[i]==true, then node i has inedges */

void MakeArc( int I,int J )         /* Create directed Edge(I,J) */
{
    Node* newnode = new Node;
    newnode->now = J;
    newnode->next = root[I].next;
    root[I].next = newnode;
}
void DFS( int n )
{
    Node* ptr = root[n].next;
    while( ptr )
    {
        if( !visited[ ptr->now ] )
        {
            visited[ ptr->now ] = 1;
            DFS( ptr->now );
        }
        ptr = ptr->next;
    }
}
void Release( Node* ptr )           /* release memory */
{
    if( ptr->next )
        Release( ptr->next );
    delete ptr;
}
int main()
{
//    freopen("D.6.dat","r",stdin);
//    freopen("out.txt","w",stdout);
    int V,E,caseN;
    int I,J;
    int count;
    ios_base::sync_with_stdio( false );
    cin>>caseN;
    while( caseN-- )
    {
        cin>>V>>E;
        memset( visited,0,sizeof(bool)*N );
        memset( indegree,0,sizeof(bool)*N );
        memset( root,0,sizeof(Node)*N );
        count = 0;
        for( int i=0;i<E;i++ )      /* graph input */
        {
            cin>>I>>J;
            MakeArc( I,J );
            indegree[J] = true;
        }
        for( int i=1;i<=V;i++ )     /* DFS through nodes with indegree zero */
            if( !indegree[i] && !visited[i] )
            {
                visited[i] = 1;
//                cout<<"Node:"<<i<<endl;
                DFS( i );
                count++;
            }
        for( int i=1;i<=V;i++ )     /* cycle detection */
            if( !visited[i] )
            {
//                cout<<"Node:"<<i<<endl;
                visited[i] = 1;
                DFS( i );
                count++;
            }
        cout<<count<<endl;
        for( int i=1;i<=V;i++ )if( root[i].next )   /* memory relaese */
            Release( root[i].next );
    }
}

Any comments are appreciated!

[andmej]

Try this case:

Code: Select all

1
4 5
1 2
2 1
3 2
3 4
4 3

Correct output is 1 (Tile #4), but your code outputs 2.

[gba356]

I changed and changed my algorithm for several times, but none of them succeeded to solve the problem

Can I have some hints?

This is driving me crazy!!

[andmej]

Reduce the original graph to a DAG where each new node corresponds to a strongly connected component of the old graph.

[wjomlex]

I'm getting RE, and I really don't see where that would be except in input formatting:

Code: Select all

import java.util.*;
import java.io.*;

public class Main
{
	static Node[] a;
	static StringTokenizer st;
	static BufferedReader scan;

	public static void main(String args[]) throws IOException
	{
		scan = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(scan.readLine());

		int t = get();

		for(int ca=0;ca < t;ca++)
		{
			int n = get();
			int k = get();

			a = new Node[n];

			for(int i=0;i < n;i++)
				a[i] = new Node();

			for(int i=0;i < k;i++)
			{
				int x = get() - 1;
				int y = get() - 1;
				
				a[x].s.push(y);
				a[y].start = false;
			}


			//process
			int rtn = 0;

			//scan for start
			for(int i=0;i < n;i++)
			{
				if(a[i].start)
				{
					rtn++;
					topple(i);
				}
			}

			//scan for cycles
			for(int i=0;i < n;i++)
			{
				if(!a[i].down)
				{
					rtn++;
					topple(i);
				}
			}

			System.out.println(rtn);
		}
	}

	public static void topple(int i)
	{
		if(a[i].down)
			return;

		a[i].down = true;

		while(!a[i].s.empty())
			topple(a[i].s.pop());
	}

	public static int get() throws IOException
	{
		while(!st.hasMoreTokens())
			st = new StringTokenizer(scan.readLine());

		return Integer.parseInt(st.nextToken());
	}
}



class Node
{
	public boolean start;
	public boolean down;
	public Stack<Integer> s;

	public Node()
	{
		start = true;
		down = false;
		s = new Stack<Integer>();
	}
}

I'm also getting RE for 11503... is there something funny with the input data formatting for these problems? I even changed my input function to skip blank lines and such.

[wjomlex]

I see I was just using too much stack space for the topple(i) method. I've changed it to a Stack implementation, and now I've improved from RE to WA. I'll have to redo my algorithm because it doesn't work on one of the Waterloo cases and I see why...

[Igor9669]

First I try to find scc(strongly connected components),with such algo:
1) Topologic sort(with dfs)
2) make graph inverse
3) dfs2 with inverse graph, this algo was written in Knuth's book, but it gived me wrang answer.
Then I don't inverse a graph and work with initial graph, this idea was right, and I got accepted!
Could somebody explain me why this was right idea????

[Obaida]

I got compile error for this problem...

Code: Select all

code.o: In function `DFS(int)':
code.cpp:(.text+0x47): relocation truncated to fit: R_X86_64_32S against symbol `visit' defined in .bss section in code.o
code.cpp:(.text+0x50): relocation truncated to fit: R_X86_64_32S against symbol `visit' defined in .bss section in code.o
code.o: In function `__tcf_1':
code.cpp:(.text+0x83): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in code.o
code.o: In function `__tcf_0':
code.cpp:(.text+0xa1): relocation truncated to fit: R_X86_64_32 against `.bss'
code.o: In function `__static_initialization_and_destruction_0(int, int)':
code.cpp:(.text+0xc9): relocation truncated to fit: R_X86_64_32 against `.bss'
code.cpp:(.text+0xe6): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in code.o
code.cpp:(.text+0xf1): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in code.o
code.cpp:(.text+0x101): relocation truncated to fit: R_X86_64_PC32 against symbol `node' defined in .bss section in code.o
code.o: In function `Topo_Sort(int)':
code.cpp:(.text+0x181): relocation truncated to fit: R_X86_64_32S against symbol `visit' defined in .bss section in code.o
code.cpp:(.text+0x18a): relocation truncated to fit: R_X86_64_32S against symbol `visit' defined in .bss section in code.o
code.cpp:(.text+0x1a3): additional relocation overflows omitted from the output
collect2: ld returned 1 exit status

someone please help me out. Here is my code:-

Code: Select all

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

struct pair{
	int l[100002],size;
}list[100002];

bool visit[100002];vector<int>node;

void Topo_Sort(int i){
	for(int j=0;j<list[i].size;j++){
		if(!visit[list[i].l[j]]){
			visit[list[i].l[j]]=1;
			Topo_Sort(list[i].l[j]);
		}
	}node.push_back(i);
}

void DFS(int i){
	for(int j=0;j<list[i].size;j++){
		if(!visit[list[i].l[j]]){
			visit[list[i].l[j]]=1;
			DFS(list[i].l[j]);
		}
	}
}

int main(){
	int t,i,a,b,m,n;scanf("%d",&t);
	while(t--){
		scanf("%d %d",&m,&n);int count=0;
		for(i=1;i<=m;i++){visit[i]=0;list[i].size=0;}
		for(i=0;i<n;i++){scanf("%d %d",&a,&b);list[a].l[list[a].size++]=b;}
		for(i=1;i<=m;i++){if(!visit[i]){visit[i]=1;Topo_Sort(i);}}
		for(i=1;i<=m;i++)visit[i]=0;
		for(i=node.size()-1;i>=0;i--){
			if(!visit[node[i]]){visit[node[i]]=1;DFS(node[i]);count++;}
		}printf("%d\n",count);node.erase(node.begin(),node.end());
	}
	return 0;
}

[helloneo]

I tried compiling your code and got this message..

Code: Select all

$ g++ 1.cpp -Wall
1.cpp:13: error: size of array 'list' is too large
1.cpp: In function 'void Topo_Sort(int)':
1.cpp:18: error: 'list' was not declared in this scope
1.cpp: In function 'void DFS(int)':
1.cpp:27: error: 'list' was not declared in this scope
1.cpp: In function 'int main()':
1.cpp:39: error: 'list' was not declared in this scope
1.cpp:40: error: 'list' was not declared in this scope

$ g++ --version
g++ (GCC) 4.2.4 (Ubuntu 4.2.4-1ubuntu3)
...

[jimmyholand88]

the dominos is very good hmmm this is a very nice info.

[vpanait]

Some advice for solving this - use STL as rarely as possible, I lost some time just profiling and replacing stl to C functions, here is some profile for the main stages of the code (the values are taken with clock() function, and represent the difference between the indication of clock() at the beginning and the end of the stage):
1. initial profile (TLE) - using std::cin, std::stack, std::list
init time is 1981
top-sort time is 8066
conn-comp time is 1638

2. code that gotAC -
replaced std::cin -> scanf()
replaced std::stack, std::list -> used vectors
init time is 94
top-sort time is 47
conn-comp time is 15

[mahade hasan]

getting wrong ans help me plz.......

Code: Select all

#include<stdio.h>
#include<iostream>
#include<vector>
#include<stack>
#include<string.h>
using namespace std;
bool Visit[100009];
vector<long>V[100009];

int main()
{
   long I,K,L,M,N,Node,Relation,Test;
   scanf("%ld",&Test);
   
   while(Test--)
   {
      N=0;
      memset(Visit,0,sizeof(Visit));
      scanf("%ld %ld",&Node,&Relation);
      M=Node;
      while(M--) V[M].clear();
      while(Relation--)
      {
         scanf("%ld %ld",&I,&K);
         V[I].push_back(K);
         V[K].push_back(I);
      }
      stack<long>S;
      for(K=1;K<=Node;K++)
      if(Visit[K]==0)
      {
        S.push(K);
        Visit[K]=1;
        ++N;
        while(!S.empty())
        {
          M=S.top();
          S.pop();
          for(I=0;I<V[M].size();I++)
          {
          if(Visit[V[M][I]]==0)
          {
            Visit[V[M][I]]=1;
            S.push(V[M][I]);
            //break;
          }
         }
       }
      }
      printf("%d\n",N);
   }
   return 0;
}

[/color]