11770 - Lighting Away

[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?

[Igor9669]

It is like scc!
Make a topologic order and then dfs!

[mukit]

thanks, Igor9669

[aliahmed]

My code accepted after using topological sort & dfs
thanx robot

[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 ?

[Igor9669]

in scc you need a reversed graph,but here you dont't need it!

[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 );

[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;
}

[robot]

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

[robot]

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...

[calicratis19]

@ robot My code works for your case.
and your case's output which you have given aliahmed is wrong.

[robot]

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...

[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

[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

[shaon3343]

I got accepted!!
can anyone find me same type of problem from other volume?