Good morning

Oh I see

Good morning...

Now I realize the algorithm is for adj list rather

I was completely tired yesterday

and highly inattentive

No, algorithm is fine for matrix as well.

Just that you need to define your loop correctly.

for (int i = 0; i < adjmatrix.size(); i++)
     if ((adjmatrix[v][i] != 0) && !visited[i])

You could even use with edge list – you'd have to iterate over all edges, though, to find the edges of interest – or if edges are sorted, you could use binary search to find starting edge and then iterate only over a sub-range...

@Aconcagua I see

Algorithms usually are designed for a problem, not for how input data is represented. Although some problems require specific data structures for internal data (Aho Corasick a modified trie, for example; but if input is std::string, array of characters or read one character by another from file is pretty irrelevant again...).

@Aconcagua right

Truth, though, is that some representations allow to perform the algorithm more efficiently than others...

I see

so for the matrix

Here: Matrix or adjacency list allow to access a specific node with O(1), while O(log n) for (sorted) edge list.

I see

I need to do another for loop inside the for loop right for the matrix version

right?

But you could, sorted edge list provided, create another array, iterate once over the list and store the starting indices in the array. Then you get O(1) vertex access again...

@Aconcagua right

Another for loop?

no

for (int i = 0; i < adjmatrix.size(); i++)
     if ((adjmatrix[v][i] != 0) && !visited[i])

this is enough

right

?

Yes.

adjlist is like a dictionary

and now I get it

Matrix is like a dictionary as well...

How?

right

only

Two-dimensional dictionary, look up if there's an edge for two specific nodes.

with 0s instead if not connected

right

If you want, you can interpret as dictionary of dictionaries as well...

right

keys are indices

it works

this is the version you talked about yesterday

cpp.sh/62rrc

so if -1

then the loop won't go

now if I want to remove the visited vector

first step is to set d(n, -1) so visited Vs will be >= 0

and we d set d[e] = 0;

But it has passed

I ll remind you later about your version

I have it in my notebook

justpaste.it/3cwnr

this it says

the first line it says

You are given an undirected unweighted graph and one of its vertexes.

I don't see "one of its vertexes" in the input

what do they mean?

Copy pase error most likely...

There's no vertex needed for this task.

so I d use dfs

Whichever you prefer...

which one suits best for the task though?

Both are fine.

I see

You start with one node and find all nodes that are reachable from that one – dfs or bfs, whichever you like better.

right

Then you look for first vertex that has not yet been visited and re-start your search from there.

but the length

And you continue like that until no unvisited nodes left any more...

i see

for bfs

the length I should use a counter variable right

?

Length?

Which length?

The next each line should contain the length of a connected component, then the component itself.

Ah, I see...

Yes, simple counter variable.

but with bfs I alreay have d

Ok

I ll see

Imagine you have a star structure. A -> B, A -> C, A -> D

Wherever you start, you have to step back somewhere...

right

I would't actually speak of 'length' of structure, that implies some kind of linearity. I'd rather use the term 'size'...

right

true

cpp.sh/8iukx

this is it

but

it lacks the counting

it outputs directly

and the count has to be the first

I tried to see every possible way

only way is a map

is that true?

but then map has unique keys, and can get same component size, so map no either

then, pair vector is the way

you could just add the values to a single vector as soon as you encounter. Then you don't have to count size separately either. Each time you start a new search, you clear that vector again...

I see

but I need to have the whole count

at the end

so for the given example

Then vector of vectors? Each time you start with a new component you add an empty inner vector to outer one and add the nodes you encounter. Outer vector.size(), then for each inner vector size + contents...

what do you think of this

geeksforgeeks.org/…

multimap of pair

Well, you then need range lookup for each component. And you would have to count number of components explicitly. With vector of vectors, you get all that for free...

right

this is vector<vector<int>> output enough, right

which way I do from here

why this is incorrect cpp.sh/2mj2o ?

sorry

missing endl;

it's wrong

cpp.sh/3pe7a

this one is ok

the previous I had a terrible notion implemented

It passed

justpaste.it/79dro

this one is a challenging task

Oh, you haven't done the knight's round trip then...

Eight moves of the knight: (x +/- 2, y +/- 1) and (x +/- 1, y +/- 2)

Note that not all fields have eight directions to leave to...

Actually, you can re-use the path problem from before.

Instead of reading an adjacency matrix, you now could create one, adding for each field an edge to its up to eight reachable other fields. Rest then is as you had before...

Calculating next fields from current one appears more efficient to me, though (that would correspond to creating only a partial matrix).

@Aconcagua you mean the problem from dynamic programming

this one

cpp.sh/8obgb

@Aconcagua this is really interesting

sorry, you meant the shortest path problem, I instantly thought that you re referring to the knight problem from the dynamic section before

@Aconcagua ok

that would be a for loop < 8

?

Not really.

(x +/- 2, y +/- 1) as well as (x +/- 1, y +/- 2)

Well, there are ways to pack that into a loop...

I see

ok

how would you do it to get it exactly

I mean

how the order would be to get the matrix

wait

isn't BFS only for unweighted graphs

?

so these are the possible moves

{ 1, 2, 2, 1, -1, -2, -2, -1 }

we also need to check the possible moves to be in the matrix

so

int X[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int Y[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

this would be the simple checker for the right moves to be inserted into the matrix

bool isInside(int x, int y, int N, int M)
{
	if (x >= 0 && x < N && y >= 0 && y < M)
		return true;
	return false;
}

but what would happen to other blocks in the matrix

or a block is already filled

and these would be the position of the knight after a move

int x = x1 + X[i];
int y = y1 + Y[i];

but how I would create the matrix, I don't have a clear idea

Don't do if(condition) return true; else return false; just have return condition;

You can iterate over each of the fields of your bord (double loop), for each field iterate over the eight neighbour offsets and if these added to current field coordinates are inside the board set a 1.

I personally wouldn't materialise that matrix, but instead iterate over the eight neighbours inside BFS and calculate them on need only. That is like calculating in the matrix only the fields that actually are needed, skipping the others.