---
# System prepended metadata

title: Some Tips of Extra/EZtra problems (5)
tags: [112計概]

---

## 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:
![image](https://hackmd.io/_uploads/ryGxxHqUa.png)

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?
![image](https://hackmd.io/_uploads/H1_J8HqL6.png)
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)


