## EZtra 2

This article will not directly provide the answer code, but will give you a few hints and explain which ideas should be inappropriate.

## Description

[Problem link](https://oj.cerana.tech/contest/6/problem/5)

Count the number of sets in a directed graph.

> If node i can reach node j,
> and node j can reach node i
>
> They are in the same set.

## Approach 1: Just DFS/BFS like HW 5-2 (WA)
Think about the following case (base 1):

4
1 0 1 0
1 1 0 0
0 1 1 1
0 0 0 1

If drawn as a picture, it would look like this:

Now imagine you are at node 3. You will find that:
* If you count every reachable node (A[i][j] or A[j][i] = 1) in the same set, the answer will be 1;
* If you count every node that is oppositely connected (A[i][j] and A[j][i] = 1), the answer will be 4.

Both of the above answers are wrong because the answer is 2

## Approach 2: DFS/BFS each node (AC)
Now to simplify the problem, what will happen if I only DFS node 1?

I can get all "reachable points" of node 1.

But how is this different from the table given at the beginning of the question?
Observe the case just given in approach 1, you will find that node 1 result is completely different.

1 0 1 0 -> 1 1 1 1

So if we can update all nodes sequentially, the table obtained at this time is almost the answer.

## To be continued...

## Approach 3: Floyd warshall (AC)

## Approach 4: Strongly Connected Component (AC, Fastest)