Page 3 of 7
Posted: 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)}.

Posted: Tue Aug 23, 2005 7:12 pm
Thank you! Thanks a lot! I was sleepy and read the description very quickly.

### 280 WA!! HELP!!

Posted: 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;
}
}
}
``````

Posted: 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

Posted: 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

Posted: Mon Jun 05, 2006 12:31 pm
Just use Flloyd Warshall (straight forward) O(n^3) or use BFS to solve this problem...

Posted: Mon Jun 05, 2006 3:50 pm
thanks, I got AC

### 280(P.E)

Posted: 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*/

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

Posted: 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]

Posted: 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
``````

Posted: Wed Jan 31, 2007 7:50 pm
sorry for my delay to response.
thank U very much for ur input.[/code][/b]

Posted: Wed Jan 31, 2007 7:54 pm
sorry for my delay to response.
thank U very much for ur input.

### 280 - Vertex Problem WA

Posted: 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];
}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)
{
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++)
{
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;
}
}
}

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++)
{
}
}
}
free(p);

return 0;
}

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

### Re: 280 - Vertex Problem WA

Posted: Fri Jun 27, 2008 7:57 am
Search the board first. Don't open a new thread if there is one already.