OJ Board

The Online Judge board
https://onlinejudge.org/board/

11770 - Lighting Away

https://onlinejudge.org/board/viewtopic.php?t=45830

Page 1 of 2

11770 - Lighting Away

Posted: Sun Jan 24, 2010 10:25 am
by mukit

Code: Select all

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>

using namespace std;

#define sz 10010
#define VI vector<int>

//DONE
I made dfs taking maximum out-degree node first.
Is my approach OK?

Re: WA in problem 11770

Posted: Sun Jan 24, 2010 12:23 pm
by Igor9669
It is like scc!
Make a topologic order and then dfs!

Re: WA in problem 11770

Posted: Sun Jan 24, 2010 4:34 pm
by mukit
thanks, Igor9669 :)

Re: WA in problem 11770

Posted: Tue Jan 26, 2010 9:01 pm
by aliahmed
My code accepted after using topological sort & dfs
thanx robot

Re: WA in problem 11770

Posted: Fri Jan 29, 2010 2:26 pm
by paaulocezar
I've tried to solve this one using two different approaches,

first one, finding the number of strongly connected components that don't have in-arcs from other scc;
and the other making kind of a topological sort, adding the vertices in a list as they're discovered in a dfs, then, each root of a tree in a dfs make following the order the vertices appear in the list is said to be one that need to be turn on.

but the two approaches are gettin' WA. some help ?

Re: WA in problem 11770

Posted: Fri Jan 29, 2010 3:06 pm
by Igor9669
in scc you need a reversed graph,but here you dont't need it!

Re: WA in problem 11770

Posted: Fri Jan 29, 2010 6:17 pm
by paaulocezar
so it's like the second way i've tried to solve,
makin a topological sort then a dfs where each spanning tree root is a light that must be turn on..
like this..

Code: Select all

REMOVED AFTER AC;

@edit..
can't believe this, I was making the worst mistake ¬¬'
my output was..
printf("%d\n", answer );
instead of
printf("Case %d: %d\n", caseNum, answer );

Re: WA in problem 11770

Posted: Sat Feb 06, 2010 10:23 pm
by calicratis19
I am getting wa in this.I am not sure if my process is ok. I used BFS.I color every node with bfs except the nodes which were the starting node of the bfs'.And then last i checked how many uncolored node is there. is it ok??

Code: Select all

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

int i,st,head,node,edge,y,x,test,kase,cur,tail;
int que[1000010];
bool flag[10010];

vector<int>adj[10001];
void BFS(int st)
{
	int i;

	head = tail = 0;
	que[tail++]=st;

	flag[st]=1;	

	while(head!=tail)
	{
		cur = que[head++];
		int	l=adj[cur].size();
		for(i=0;i<l;i++)
		{
			if(!flag[adj[cur][i]])
			{
				que[tail++] = adj[cur][i];
				flag[adj[cur][i]]=1;
			}
		}
	}
	flag[st]=0;	
}

int main()
{
	//freopen("in.txt","r",stdin);
//	freopen("b.txt","w",stdout);
	scanf("%d",&test);

	while(test--)
	{

		scanf("%d %d",&node,&edge);
		for(i=0;i<=node;i++)
		{
			adj[i].clear();flag[i]=0;
		}

		for(i=1;i<=edge;i++)
		{
			scanf("%d %d",&x,&y);
			adj[x].push_back(y);
		}

		for(i=1;i<=node;i++)
			if(!flag[i])
				BFS(i);

		st = 0;
		for(i=1;i<=node;i++)if(!flag[i])st++;

		printf("Case %d: %d\n",++kase,st);
		
	}
	return 0;
}

Re: WA in problem 11770

Posted: Sun Feb 07, 2010 8:29 am
by robot
calicratis19 wrote:I am getting wa in this.I am not sure if my process is ok. I used BFS.I color every node with bfs except the nodes which were the starting node of the bfs'.And then last i checked how many uncolored node is there. is it ok??

Code: Select all

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

int i,st,head,node,edge,y,x,test,kase,cur,tail;
int que[1000010];
bool flag[10010];

vector<int>adj[10001];
void BFS(int st)
{
	int i;
	head = tail = 0;

	que[tail++]=st;
	while(head!=tail)
	{
		cur = que[head++];
		int	l=adj[cur].size();
		for(i=0;i<l;i++)
		{
			if(!flag[adj[cur][i]] && adj[cur][i]!=st)
			{
				que[tail++] = adj[cur][i];
				flag[adj[cur][i]]=1;
			}
		}
	}
	
}

int main()
{
	scanf("%d",&test);
	while(test--)
	{

		scanf("%d %d",&node,&edge);
		for(i=0;i<=node;i++)
		{
			adj[i].clear();flag[i]=0;
		}

		for(i=1;i<=edge;i++)
		{
			scanf("%d %d",&x,&y);
			adj[x].push_back(y);
		}

		for(i=1;i<=node;i++)
			if(!flag[i])
				BFS(i);

		st = 0;
		for(i=1;i<=node;i++)if(!flag[i])st++;

		printf("Case %d: %d\n",++kase,st);
		
	}
	return 0;
}

Hi, calica...
try this input
1
7 8
1 4
4 3
3 1
2 1
2 5
5 2
6 5
7 3
output: 2

i think that u do topological sort concept, Ist u lighting the all zero indegree, then lighting the maxi outdegree, if outdegree and indegree are same u give priority the outdegree, then indegree or u can use vertex cover tecnique(SCC).

Re: WA in problem 11770

Posted: Sun Feb 07, 2010 8:38 am
by robot
aliahmed wrote:Getting WA?

#include<stdio.h>

long front,rear,f[10000],grid[10000][10000],ind[10000],q[100000],m,n,t,l,p[11000],a,b,visit[10000],c=0,cas=1;

void dfs(long k)
{
long u,l;
u=k;
for(l=1; l<p; l++)
{
if(!visit[grid[l]])
{
visit[grid[l]]=1;
//printf("%ld ",grid[l]);
dfs(grid[l]);
}
}
}

void t_sort()
{
long i,j;
front=1; rear=1;
for(i=1; i<=m; i++)
{

if(ind==0 && f==1)
{
q[rear++]=i;
visit=1;
}
}
l=rear;
for(i=1; i<=rear; i++)
{
for(j=1; j<=p[q[front]]; j++)
{
if(f[j]==1)
{
ind[grid[q[front]][j]]--;
if(ind[grid[q[front]][j]]==0)
q[rear++]=grid[q[front]][j];

}
}
front++;
}
c=0;
for(i=1; i<rear; i++)
{
if(visit[q]==0)
{
dfs(q);
c++;
}
}
printf("Case %ld: %ld\n",cas++,c);
}


int main()
{
long i,j;
scanf("%ld",&t);
while(t--)
{
scanf("%ld%ld",&m,&n);

for(i=1; i<=m; i++) {ind=0; p=1; f=0; visit=0;}

for(i=1; i<=n; i++)
{
scanf("%ld%ld",&a,&b);
grid[a][p[a]++]=b;
f[a]=1;
f=1;
ind++;
}
t_sort();
}

return 0;
}


Hi, aliahmed
try this input:
2
7 8
1 4
4 3
3 1
2 1
2 5
5 2
6 5
7 3
5 1
1 2
output:
Case 1: 2
Case 2: 4
u can do topological sort concept...

Re: WA in problem 11770

Posted: Sun Feb 07, 2010 8:59 am
by calicratis19
@ robot My code works for your case.
and your case's output which you have given aliahmed is wrong.

Re: WA in problem 11770

Posted: Sun Feb 07, 2010 8:33 pm
by robot
robot wrote:
aliahmed wrote:Getting WA?

#include<stdio.h>

long front,rear,f[10000],grid[10000][10000],ind[10000],q[100000],m,n,t,l,p[11000],a,b,visit[10000],c=0,cas=1;

void dfs(long k)
{
long u,l;
u=k;
for(l=1; l<p; l++)
{
if(!visit[grid[l]])
{
visit[grid[l]]=1;
//printf("%ld ",grid[l]);
dfs(grid[l]);
}
}
}

void t_sort()
{
long i,j;
front=1; rear=1;
for(i=1; i<=m; i++)
{

if(ind==0 && f==1)
{
q[rear++]=i;
visit=1;
}
}
l=rear;
for(i=1; i<=rear; i++)
{
for(j=1; j<=p[q[front]]; j++)
{
if(f[j]==1)
{
ind[grid[q[front]][j]]--;
if(ind[grid[q[front]][j]]==0)
q[rear++]=grid[q[front]][j];

}
}
front++;
}
c=0;
for(i=1; i<rear; i++)
{
if(visit[q]==0)
{
dfs(q);
c++;
}
}
printf("Case %ld: %ld\n",cas++,c);
}


int main()
{
long i,j;
scanf("%ld",&t);
while(t--)
{
scanf("%ld%ld",&m,&n);

for(i=1; i<=m; i++) {ind=0; p=1; f=0; visit=0;}

for(i=1; i<=n; i++)
{
scanf("%ld%ld",&a,&b);
grid[a][p[a]++]=b;
f[a]=1;
f=1;
ind++;
}
t_sort();
}

return 0;
}


Hi, aliahmed
try this input:
1
5 1
1 2
output: 4
u can do topological sort concept...

Re: WA in problem 11770

Posted: Tue Feb 16, 2010 11:34 pm
by Taman
@calicratis19:
Well, you should try this case,
1
4 5
1 2
2 1
2 3
3 2
4 2

The output should be 1, where your code prints 2. . .
Hope it helps :)

Re: WA in problem 11770

Posted: Sat Feb 20, 2010 12:45 pm
by arifcsecu
My approach is something as like as Robot.

Algorithm:
1. run dfs for every zero in-degree vertex
and count all zero in-degree vertex.
2. run dfs for maximum out-degree vertex ( if it has not visited yet and increase the counter)

3. run dfs for all vertices which has not visited yet and increase the counter.

Test Case:
1
8 6
2 8
8 7
7 2
3 6
6 4
4 3

Output:
Case 1: 4

Re: WA in problem 11770

Posted: Sat Feb 27, 2010 6:45 am
by shaon3343
I got accepted!! :D :D
can anyone find me same type of problem from other volume?
All times are UTC+02:00
Page 1 of 2

Powered by phpBB® Forum Software © phpBB Limited