### 11518 - Dominos 2

Posted:

**Fri Mar 06, 2009 12:53 pm**The UVa Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=50&t=42640

Page **1** of **2**

Posted: **Fri Mar 06, 2009 12:53 pm**

Posted: **Fri Mar 06, 2009 8:21 pm**

Just think that, you can run the bfs or dfs only once. As I see that you are calling the bfs l times.

Posted: **Sat Mar 07, 2009 6:35 am**

how ?Just think that, you can run the bfs or dfs only once. As I see that you are calling the bfs l times.

if sources be different

like this:

Code: Select all

```
1
7 4 2
1 2
2 3
4 5
5 6
2
4
```

Posted: **Sat Mar 07, 2009 6:51 am**

Sorry. I actually wanted to say that
In this line when bfs is called then all the values will be copied in **vector< vector < int > > a**. So, each time a bfs is called, a huge number of values will be copied. So, you can store 'a' as global or simply pass the reference, then only the address will be provided not the whole values. Just change the line to
Hope it helps.

Code: Select all

`int bfs(int i,vector< vector < int > > a)`

Code: Select all

`int bfs(int i,vector< vector < int > > &a) // Check that the reference is passed`

Posted: **Sat Mar 07, 2009 7:00 am**

Thanks Jan

Posted: **Sat Apr 04, 2009 5:53 pm**

anyone help plz i'm getting WA for this problem.

Code: Select all

```
#include<stdio.h>
#include<string.h>
#include<vector>
#include<list>
using namespace std;
#define _pf printf
#define _sc scanf
#define max 10002
int n,m,l,C;
list<int> L[max];
bool map[max];
bool check[max];
void dfs(int i){
int r;
C++;
map[i]=false;
list<int>::iterator It;
for(It=L[i].begin();It!=L[i].end();It++){
r=(*It);
if(map[r]){
dfs(r);
}
}
}
int main(){
int T,x,y,z,S;
_sc("%d",&T);
while(T--){
memset(map,true,sizeof(map));
memset(check,true,sizeof(check));
S=0;
_sc("%d %d %d",&n,&m,&l);
while(m--){
_sc("%d %d",&x,&y);
if(x>n || y>n) continue;
L[x].push_back(y);
}
while(l--){
_sc("%d",&z);
if(z>n)continue;
if(check[z]){
C=0;
check[z]=false;
dfs(z);
S+=C;
}
}
_pf("%d\n",S);
for(int i=0;i<max;i++)
L[i].clear();
}
return 0;
}
```

Posted: **Sun Oct 10, 2010 5:01 pm**

Hi tanmoy...You just made a silly mistake...

Check ur bool map array !!!!!!!!!!!

- IMPOSSIBLE MEANS I M POSSIBLE....

Posted: **Wed Oct 20, 2010 9:50 am**

Run simple dfs. Be very careful about flagging. if one domino has fallen,it cant fall once again

Posted: **Wed Nov 03, 2010 9:11 pm**

Note:

Here, z's aren't unique.Each of the following l lines contains a single integer z indicating that the domino numbered z is knocked over by hand.

Posted: **Sat Jan 22, 2011 7:56 pm**

I get TLE...Help me...I can't understand how can I reduce the time....here is my code....

#include<stdio.h>

#include <iostream>

#include <queue>

using namespace std;

int r,s,i,j,k,n,m,cas,l,l1,N,G[10001][10001],co,v[10001],flag,f[10001],lp;

queue<int> q;

void BFS(int start_v, int n)

{

v[start_v]=1;

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

if(G[start_v]* == 1 && v** == 0)*

{ q.push(i);

v* = 1;*

co++;

}

}

while(!q.empty())

{

int tmp = q.front();

q.pop();

BFS(tmp,n);

}

}

int main(){

scanf("%d",&cas);

for(l1=0;l1<cas;l1++){

scanf("%d %d %d",&N,&m,&l);

for(i=0;i<N;i++)

for(j=i;j<N;j++)

G*[j]=G[j]**=0;*

for(i=0;i<m;i++){

scanf("%d %d",&r,&s);

G[r-1][s-1]=1;

}

for(i=0;i<l;i++){

scanf("%d",&co);

f*=co-1; *

}

for(i=0;i<N;i++)

v*=0;*

lp=l;

co=0;

for(k=0;k<l;k++){

j=f[k];

if(v[j]==1){

lp--;

continue;}

v[j]=1;

BFS(j,N);

}

printf("%d\n",co+lp);

}

return 0;

}

#include<stdio.h>

#include <iostream>

#include <queue>

using namespace std;

int r,s,i,j,k,n,m,cas,l,l1,N,G[10001][10001],co,v[10001],flag,f[10001],lp;

queue<int> q;

void BFS(int start_v, int n)

{

v[start_v]=1;

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

if(G[start_v]

{ q.push(i);

v

co++;

}

}

while(!q.empty())

{

int tmp = q.front();

q.pop();

BFS(tmp,n);

}

}

int main(){

scanf("%d",&cas);

for(l1=0;l1<cas;l1++){

scanf("%d %d %d",&N,&m,&l);

for(i=0;i<N;i++)

for(j=i;j<N;j++)

G

for(i=0;i<m;i++){

scanf("%d %d",&r,&s);

G[r-1][s-1]=1;

}

for(i=0;i<l;i++){

scanf("%d",&co);

f

}

for(i=0;i<N;i++)

v

lp=l;

co=0;

for(k=0;k<l;k++){

j=f[k];

if(v[j]==1){

lp--;

continue;}

v[j]=1;

BFS(j,N);

}

printf("%d\n",co+lp);

}

return 0;

}

Posted: **Thu Nov 03, 2011 11:18 am**

Keep an array of Domino objects. Each one has a boolean indicating whether or not it has been knocked down, and a stack of integers that are the indices of the dominoes that it will knock down.

Then for each domino that's knocked down, run a recursive function that knocks down all dominoes that are in the first domino's stack. Don't knock down dominoes that have previously been knocked down. For each domino knocked down, increment a running total.

Then for each domino that's knocked down, run a recursive function that knocks down all dominoes that are in the first domino's stack. Don't knock down dominoes that have previously been knocked down. For each domino knocked down, increment a running total.

Posted: **Mon Nov 21, 2011 5:34 pm**

Run BFS single time for all domino's which are knocked over by hand.

If you run BFS l time then you got time limit exit.

First push all z to queue then run bfs one time and calculate total number of domino's fall down.

If you run BFS l time then you got time limit exit.

First push all z to queue then run bfs one time and calculate total number of domino's fall down.

Posted: **Thu May 17, 2012 9:49 pm**

cutt>>>ACC

Posted: **Fri May 18, 2012 12:23 am**

If Mat can only be 0 or 1 then make it type bool.

Posted: **Fri May 18, 2012 7:28 pm**

thanx for ur kind reply

Can You give some I/O?

Can You give some I/O?