280 - Vertex

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Aug 23, 2005 9:11 am

Read very carefully this part of the problem statement:
Each set represent a collection of edges. The first integer in the set, i, is the starting vertex, while the next group of integers, j...k, define the series of edges i -> j ... i -> k.
For instance, the graph in the sample input has the edges: {(1,2), (2,2), (3,1), (3,2)}.

User avatar
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by Jemerson » Tue Aug 23, 2005 7:12 pm

Thank you! Thanks a lot! I was sleepy and read the description very quickly.
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

280 WA!! HELP!!

Post by shihabrc » Sun Oct 09, 2005 5:48 pm

I've tried various types of input. I've also tried the I/O provided in the board. All gives correct output. But still getting WA. plz help.

Code: Select all

#include<stdio.h>
#define SIZE 300

int mat[SIZE][SIZE];
int count;
int visited[SIZE];
int n;
int col[SIZE];
int v[SIZE];

void init(void);
void dfs(int);
void visit(int);
void initmat(void);

void main(void){
	int cnt,i,j,p=0,row;
	freopen("C:\\3.txt","rb",stdin);
	freopen("C:\\33.txt","w",stdout);
	while(scanf("%d",&n)==1){
		if(!n) break;
		initmat();
		for(i=0;i<=n;i++){
			scanf("%d",&row);
			if (!row) break;
			else {
				for(j=0;j<=n;j++){
					scanf("%d",&col[j]);
					if(!col[j]) break;
					mat[row-1][col[j]-1]=1;
				}
			}
		}
		scanf("%d", &cnt);
		for(i=0;i<cnt;i++){
			scanf("%d", &v[i]);
		}
		p=0;
		do{
			count=0;
			init();
			dfs(v[p]);
			printf("%d ",n-count);
			for(i=0;i<n;i++){
				if(!visited[i]) {
					printf("%d ",i+1);
				}
			}
			printf("\n");
			p++;
		} while(p<cnt);
	}
}


void dfs(int i){
	if (!visited[i-1]){
		visit(i-1);
	}
}


void visit(int u){
	int i;
	for(i=0;i<n;i++){
		if(mat[u][i] && !visited[i]){
			visited[i]=1;
			visit(i);
			count++;
		}
	}
}


void init(){
	int i;
	for(i=0;i<SIZE;i++){
		visited[i]=0;
	}
}


void initmat(void){
	int i,j;
	for(i=0;i<SIZE;i++){
		for(j=0;j<SIZE;j++){
			mat[i][j]=0;
		}
	}
}

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Fri Jun 02, 2006 2:24 pm

hello,
why my code was TLE ?
STL makes it islow ?
or an endless loop ?

Code: Select all


#include <iostream>
#include <vector>
#include <algorithm>

#define SIZE 101

using namespace std;


void printv( const vector<int> &v )
{
	for( vector<int>::const_iterator e = v.begin(); e != v.end(); e++ )
		cout << *e << " ";
}


void dfs_visit( const vector<int> *g, int curr, vector<int> &unreached )
{
	for( vector<int>::const_iterator e = g[curr].begin(); e != g[curr].end(); e++ )
		{
			vector<int>::iterator tmp = find( unreached.begin(), unreached.end(), *e );
			if( tmp != unreached.end() )	
				{
					unreached.erase( tmp );
					dfs_visit( g, *e, unreached );
				}
		}
}			


void dfs( const vector<int> *graph, int last, int start )
{
	vector<int> unreached;
	for( int w = 1; w <= last; w++ )
		unreached.push_back(w);

	dfs_visit( graph, start, unreached );
	cout << unreached.size() << " ";
	printv( unreached );
	cout << endl;
}


int main()
{
	int nvert, tmp, index, ntest;
	vector<int> graph[SIZE];

	cin >> nvert;
	while( nvert )
		{
			cin >> index;
			while( index )
				{
					cin >> tmp;
					while( tmp )
						{
							graph[index].push_back( tmp );
							cin >> tmp;
						}
					cin >> index;
				}

			cin >> ntest;
			while( ntest-- )
				{
					cin >> tmp;
					dfs( graph, nvert, tmp );
				}

			for( int w = 1; w <= nvert; w++ )
				graph[w].clear();
			cin >> nvert;
		}

	return 0;
}
							
	
thanks
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Fri Jun 02, 2006 4:17 pm

hello, I have some input test cases... but my code received TLE, anyway:
input:
7
1 2 0
2 3 4 0
3 1 0
4 5 0
5 4 0
6 7 0
7 6 0
0
7 1 2 3 4 5 6 7
5
0
5 1 2 3 4 5
4
1 2 3 4 0
2 3 4 0
3 4 0
0
4 1 2 3 4
3
1 2 0
2 2 0
3 1 2 0
0
2 1 2
4
1 2 0
2 3 0
3 4 0
0
2 2 1
5
1 2 0
2 3 0
3 4 0
4 5 0
1 1 0
0
1 1
0
output:
2 6 7
2 6 7
2 6 7
5 1 2 3 6 7
5 1 2 3 6 7
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
1 1
2 1 2
3 1 2 3
4 1 2 3 4
2 1 3
2 1 3
2 1 2
1 1
0
I'm keep trying, I hope you too
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Mon Jun 05, 2006 12:31 pm

Just use Flloyd Warshall (straight forward) O(n^3) or use BFS to solve this problem...

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Mon Jun 05, 2006 3:50 pm

thanks, I got AC :D :lol:
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

zaman
New poster
Posts: 8
Joined: Sun Jan 07, 2007 5:40 am
Location: dhaka

280(P.E)

Post by zaman » Mon Jan 08, 2007 10:02 pm

Hi,everyone. I've got several times P.E. in this problem.Any help will be appreciated.Here is my code:
/* Code has been removed after acc*/

Thanks in advance.Please reply soon!!!!
Last edited by zaman on Wed Jan 31, 2007 8:04 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jan 08, 2007 10:29 pm

A few points:
1. There are already a few threads on problem 280, why not post in one of them? In case you haven't noticed, forum's description says "If there is a thread about your problem, please use it."

2. Please use [ code] [/code] tags when pasting code. It's completely unreadable without them.

3. You got PE because your program prints unnecessary blank lines.

zaman
New poster
Posts: 8
Joined: Sun Jan 07, 2007 5:40 am
Location: dhaka

Post by zaman » Wed Jan 10, 2007 5:04 am

Thanks for ur reply.please show me the difference in your acc output and my output for some inputs.[/code]

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Jan 10, 2007 5:54 am

On this input your code prints an unnecessary blank line:

Code: Select all

3
1 2 0
2 2 0
3 1 2 0
0
2 1 2
3
1 2 0
2 2 0
3 1 2 0
0
0
3
1 2 0
2 2 0
3 1 2 0
0
2 1 2
0

zaman
New poster
Posts: 8
Joined: Sun Jan 07, 2007 5:40 am
Location: dhaka

Post by zaman » Wed Jan 31, 2007 7:50 pm

sorry for my delay to response.
thank U very much for ur input.[/code][/b]

zaman
New poster
Posts: 8
Joined: Sun Jan 07, 2007 5:40 am
Location: dhaka

Post by zaman » Wed Jan 31, 2007 7:54 pm

sorry for my delay to response.
thank U very much for ur input.

mjochem
New poster
Posts: 1
Joined: Thu Jun 26, 2008 11:51 pm

280 - Vertex Problem WA

Post by mjochem » Thu Jun 26, 2008 11:57 pm

Can anyone help me with this problem?
I don't have much experience with algorithms and uva problems...

I've tested this program with many inputs, but I'm still getting wa...

Here's my code (i'm used dfs):

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define TAM 200

typedef struct no{
	int caminhos[TAM];
	int visitado;
}vertice;

vertice *p;

int alcancavel;

void DFS (int i)
{
	int j;
	j = 0;
	while(p[i].caminhos[j] >= 0 && p[p[i].caminhos[j]].visitado == -1)
	{
		p[p[i].caminhos[j]].visitado = 1;
		alcancavel++;
		DFS(p[i].caminhos[j]);
		j++;
	}
}

void fazDFS (int N, int inicio)
{
	int i;
	DFS(inicio);
	printf("%d", N-alcancavel);
	for(i = 1; i <= N; i++)
	{
		if(p[i].visitado == -1)
			printf(" %d", i);
	}
	printf("\n");
}

void atualiza()
{
	int i, j;
	for(i = 0; i < TAM; i++)
	{
		for(j = 0; j < TAM; j++)
		{
			p[i].caminhos[j] = -1;
		}
		p[i].visitado = -1;
	}
}

int main()
{
	int N, i, e, j;

	p = (vertice *) malloc (TAM * sizeof (vertice) );

	while(scanf("%d", &N) == 1 && N)
	{
		atualiza();

		while(scanf("%d", &i) == 1 && i)
		{
			while(scanf("%d", &e) == 1 && e)
			{
				j = 0;
				while(p[i].caminhos[j] >= 0)
					j++;
				p[i].caminhos[j] = e;
			}
		}
		scanf("%d", &i);
		while(i-- > 0)
		{
			scanf("%d", &j);
			alcancavel = 0;
			fazDFS (N,j);
			for(e=0; e <= N; e++)
			{
				p[e].visitado=-1;
			}
		}
	}
	free(p);
	
	return 0;
}	

I will be very grateful with some help!!
[]'s

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 280 - Vertex Problem WA

Post by Jan » Fri Jun 27, 2008 7:57 am

Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 2 (200-299)”