280 - Vertex

[RubenRamalho]

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?

[Edit] Nevermind got it aldready

[BUET]

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]

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

[vo_minhdat2007]

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) {
		// Read edges
		int startVertex = pScanner.nextInt() - 1;
		while (startVertex >= 0) {
			
			int endVertex = pScanner.nextInt() - 1;
			while (endVertex >= 0) {
				mAdjacentVertexes[startVertex].value.add(endVertex);
				
				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
			readData(scanner);
			
			// 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]

What happens if count is 0?

[@ce]

Getting WA...plzzz help.

Code: Select all

AC

[brianfry713]

Try input:

Code: Select all

1
1 1 0
0
1 1
1
0
1 1
0

[@ce]

Thanx..i got my mistake.

[armankashef]

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]

input:

Code: Select all

1
1 1 0
0
1 1
1
0
1 1
0

correct output:

Code: Select all

0
1 1

[armankashef]

thanx for your help
can help me more

[armankashef]

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]

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

[AKJ88]

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]

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