280 - Vertex

[mf]

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

[Jemerson]

Thank you! Thanks a lot! I was sleepy and read the description very quickly.

[shihabrc]

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]

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

[beloni]

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

[jan_holmes]

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

[beloni]

thanks, I got AC

[zaman]

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

[mf]

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]

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

[mf]

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]

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

[zaman]

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

[mjochem]

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]

Search the board first. Don't open a new thread if there is one already.