Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

第三題 #4

Open
Stephen-Shen opened this issue Dec 1, 2017 · 6 comments
Open

第三題 #4

Stephen-Shen opened this issue Dec 1, 2017 · 6 comments

Comments

@Stephen-Shen
Copy link

第二組負責
@hao860524
Copy link

HW9.pptx

@c910335
Copy link
Member

c910335 commented Dec 3, 2017

1.找出這個有向圖的Maximal SCCs

SCC 已經有 Maximal 的意思在了
我想是沒有必要再特別強調 Maximal

時間複雜度的部分請再說明得更清楚點
1 2 4 都不用花時間嗎？

@hao860524
Copy link

image
以上執行兩次DFS，在上圖方法的第三步SCC graph可以找出edge

所以我們投影片的1~2 =>O(|V|+|E|)

4 SCC graph G‘=(U,E’)，U是component的集合
=>O(|U|)

以上是我的想法

@scps940707
Copy link
Member

早安～你們有打算更新投影片嗎？

@hao860524
Copy link

HW9.pptx

@jimmylu1220
Copy link

HW9.pptx

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@c910335 @scps940707 @hao860524 @Stephen-Shen @jimmylu1220