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

RubenRamalho
New poster
Posts: 4
Joined: Fri Jun 25, 2010 8:33 pm

### Re: 280 Vertex WA Help!!

I'm getting WA with this one and it is working for the inputs posted here, also if anyone knows, how can I solve this problem more efficiently?

 Nevermind got it aldready

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

### 280 Vertex TLE Help!!

Code: Select all

``````#include<iostream>
#include<vector>
#include<list>

using namespace std ;

void DFS( int u );

int info[100][100] = {0} ;

bool color[100] = {false};

int node_degree[100] = {0};
int main (void)
{
int vert,count;

list <int> print ;
int v;

int neigh;

int a,i,k,l;

cin >> vert ;

while(vert)
{

cin >> v ;

while (v)
{
cin >> neigh;

while ( neigh )
{
node_degree[v]++ ;

info[v][ node_degree[v] ] = neigh;

cin >> neigh;
}

cin >> v;
}

cin >> count ;

vector <int> vec ;

while ( count-- )
{
cin >> a ;

vec.push_back( a );
}

vector<int>::const_iterator e;
for(  e = vec.begin(); e != vec.end(); e++ )
{

i =  *e;

DFS(i);

for( k = 1; k <= vert; k++ )
{
if( color[k] == false )
{
print.push_back(k);

}
}

list < int > :: iterator p = print.begin();

cout << print.size() << " " ;

while( p != print.end() )
{
cout << *p << " ";

p++;
}

cout << "\n";

print.clear();

memset(color,false,sizeof(color));
}

vec.clear();

cin >> vert;
}
return 0;
}

void DFS(int u)
{
int v ;

for( v = 1; v <= node_degree[u] ; v++ )
{
if( !color[ info[u][v] ] )
{
color[ info[u][v] ] = true;

DFS( info[u][v]) ;
}
}
}
``````

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 280 Vertex WA Help!!

i can't figure it out what's wrong in my code. i used DFS using a adjacency list in a quite straightforward approach. plz someone help me

Code: Select all

``````AC
``````
Do or do not. There is no try.

vo_minhdat2007
New poster
Posts: 5
Joined: Mon Apr 09, 2012 7:11 am

### 280 - Vertex Presentation Error?

Here is the link for problem: http://uva.onlinejudge.org/index.php?op ... D+10004212

This is my code:

Code: Select all

``````import java.util.ArrayList;
import java.util.Scanner;

import javax.swing.SpringLayout.Constraints;

public class Main {

//=======================================================//
// Inner Class
//=======================================================//

public class ArrayListInteger {
public ArrayList<Integer> value = new ArrayList<Integer>();
}

//=======================================================//
// Variables
//=======================================================//

private static boolean[] mIsVisited;
private static int mVertexCount;
private static ArrayListInteger[] mAdjacentVertexes;
private static int[] mStartVertex;

//=======================================================//
// Public Methods
//=======================================================//

public static void readData(Scanner pScanner) {
int startVertex = pScanner.nextInt() - 1;
while (startVertex >= 0) {

int endVertex = pScanner.nextInt() - 1;
while (endVertex >= 0) {

endVertex = pScanner.nextInt() - 1;
}

startVertex = pScanner.nextInt() - 1;
}

// Read start vertexes
int numberOfStart = pScanner.nextInt();
mStartVertex = new int[numberOfStart];
for (int i = 0; i < numberOfStart; i++) {
mStartVertex[i] = pScanner.nextInt() - 1;
}
}

public static void dfs(int pStartVertex, boolean pIsFirstVertex) {
if (!pIsFirstVertex)
mIsVisited[pStartVertex] = true;
for (int i = 0; i < mAdjacentVertexes[pStartVertex].value.size(); i++) {
int currentVertex = mAdjacentVertexes[pStartVertex].value.get(i);
if (!mIsVisited[currentVertex])
dfs(currentVertex, false);
}
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
StringBuilder result = new StringBuilder();

mVertexCount = scanner.nextInt();
while (mVertexCount > 0) {
// Intialize
mAdjacentVertexes = new ArrayListInteger[mVertexCount];
Main temp = new Main();
for (int i = 0; i < mVertexCount; i++) {
mAdjacentVertexes[i] = temp.new ArrayListInteger();
}

// Read remaining Data

// Traverse
for (int i = 0; i < mStartVertex.length; i++) {
mIsVisited = new boolean[mVertexCount];
dfs(mStartVertex[i], true);

StringBuilder subResult = new StringBuilder();
int count = 0;
for (int j = 0; j < mIsVisited.length; j++) {
if (mIsVisited[j]) continue;
count++;
subResult.append(j + 1);
subResult.append(" ");
}
// Remove last space
if (subResult.length() > 0)
subResult.deleteCharAt(subResult.length() - 1);

result.append(count);
result.append(" ");
result.append(subResult);
result.append("\n");
}

// Read next data
mVertexCount = scanner.nextInt();
}

System.out.print(result.toString());
}

}
``````
A sample input:

Code: Select all

``````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
0
``````
My program 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
Please tell me why I get presentation error?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 280 - Vertex Presentation Error?

What happens if count is 0?
Check input and AC output for thousands of problems on uDebug!

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 280 - Vertex Presentation Error?

Getting WA...plzzz help.

Code: Select all

``````AC
``````
Last edited by @ce on Tue Oct 09, 2012 3:02 am, edited 1 time in total.
-@ce

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 280 - Vertex Presentation Error?

Try input:

Code: Select all

``````1
1 1 0
0
1 1
1
0
1 1
0``````
Check input and AC output for thousands of problems on uDebug!

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 280 - Vertex Presentation Error?

Thanx..i got my mistake.
-@ce

armankashef
New poster
Posts: 10
Joined: Tue Jun 05, 2012 9:33 pm

### 280 - Vertex

why I getting WA

Code: Select all

``````#include <iostream>
#include <math.h>
#include <string>
#include <string.h>
#include <stdio.h>
using namespace std ;
int mat[101][101] , q[101] ;
bool  mark[101] ;
int f = 0 ;
void dfs(int u,int b)
{
if( f )
mark[u] = true;
int v ;
for(v = 0; v < b ; v ++)
if( mark[v] == false && mat[u][v] == 1 )
{
f++ ;
dfs(v,b);
}
}
int main()
{
int n , i , j = 1 , v , u , x ;
while( cin >> n , n )
{
memset( mat , 0 , sizeof( mat ) ) ;
while( cin >> v , v )
while( cin >> u , u )
mat[v-1][u-1] = 1 ;
cin >> x ;
int k , c ,count = 0;
while( x-- )
{
cin >> j ;
count = 0 ;
f = 0 ;
dfs( j-1 , n ) ;
for( c = 0 ; c < n ; c++ )
if( mark[c] == 0 )
count++ ;
cout << count ;
for( c = 0 ; c < n ; c++ )
if( mark[c] == 0 )
cout << " " << c + 1 ;
cout << endl ;
}
}
return 0 ;
}``````
Help me plz

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 280 - Vertex

input:

Code: Select all

``````1
1 1 0
0
1 1
1
0
1 1
0``````
correct output:

Code: Select all

``````0
1 1``````
Check input and AC output for thousands of problems on uDebug!

armankashef
New poster
Posts: 10
Joined: Tue Jun 05, 2012 9:33 pm

### Re: 280 - Vertex

thanx for your help
can help me more

armankashef
New poster
Posts: 10
Joined: Tue Jun 05, 2012 9:33 pm

### Re: 280 - Vertex

I change my code
to this
but still WA

Code: Select all

``````    #include <iostream>
#include <math.h>
#include <string>
#include <string.h>
#include <stdio.h>
using namespace std ;
int mat[101][101] , q[101] ;
bool  mark[101] ;
int f = 0 ;
void dfs(int u,int b)
{
if( f )
mark[u] = true;
int v ;
for(v = 0; v < b ; v ++)
if( mark[v] == false && mat[u][v] == 1 )
{
f++ ;
dfs(v,b);
}
}
int main()
{
int n  , j = 1 , v , u , x ;
while( cin >> n , n )
{
memset( mat , 0 , sizeof( mat ) ) ;
memset( mark , 0 , sizeof( mark ) ) ;
while( cin >> v , v )
while( cin >> u , u )
mat[v-1][u-1] = 1 ;
cin >> x ;
int k , c ,count = 0;
while( x-- )
{
cin >> j ;
count = 0 ;
f = 0 ;
dfs( j-1 , n ) ;
for( c = 0 ; c < n ; c++ )
{
if( mark[c] == 0 )
{
count++ ;
}
}
cout << count ;
for( c = 0 ; c < n ; c++ )
{
if( mark[c] == 0 )
{
cout << " " << c + 1 ;
}
}
cout << endl ;
}
}
return 0 ;
}``````
help me plz

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 280 - Vertex

input

Code: Select all

``````3
1 2 0
2 1 0
0
3 1 2 3
0``````
Correct output

Code: Select all

``````1 3
1 3
3 1 2 3``````
Check input and AC output for thousands of problems on uDebug!

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

### Re: 280 - Vertex

My program prints the correct result for sample inputs posted here, but still WA
Can anyone help me please? Thanks.

Code: Select all

``````#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

int N;
vector< int > edges[105];
bool visited[105];

void dfs(int v){
int u, i;
for(i=0; i<edges[v].size(); i++){
u = edges[v][i];
if(!visited[u]){
visited[u] = true;
dfs(u);
}
}
}

int main(){
#ifndef ONLINE_JUDGE
freopen("J:\\acm\\vertex.in", "r", stdin);
#endif // !ONLINE_JUDGE
int u, v, I, J, count, inaccVertices;
char ouput[210];

while( scanf("%d", &N) && N ){
do{
scanf("%d", &u);
while( u && scanf("%d", &v) && v )
edges[u].push_back(v);
}while(u);

scanf("%d", &count);
while( count-- ){
scanf("%d", &u);
memset(visited, 0, sizeof(visited));
dfs(u);
inaccVertices = 0;
J = -1;
for(I=1; I<=N; I++){
if(!visited[I]){
inaccVertices ++;
J++;
ouput[J++] = I + '0';
ouput[J] = ' ';
}
}
if(J==-1)
J ++;
ouput[J] = 0;
printf("%d %s\n", inaccVertices, ouput);
}
memset(edges, 0, sizeof(edges));
}

return 0;
}

``````

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

### Re: 280 - Vertex

Never mind! I got it!!!
A teeny tiny, but in a way terribly big mistake!