# DSA-HW4-NonProgrammingPart
## B07902060 資工一 趙雋同
### Problem 1. k-th Largest Element
#### 1.

typedef struct RBtree{
	int color;
	int value;
	int descendants;
	struct RBtree *left , *right , *parent;
}rb;
int sz(rb *root){
	if(root == NULL)
		return 0;
	root->descendants = sz(root->left) + sz(root->right) + 1;
	return root->descendants;
}

利用遞迴遍歷整棵RB tree，如果root是NIL的話，就return 0代表該節點沒有子孫，若不是NIL的話，即為其左右子孫的descendants的數量加上自己（+1）。由於每個節點只會走到一次，所以time-complexity是O(n).

#### 2.
由於需要變動的sz(x)只有插入時被訪問到的節點，且紅黑數的高度為$O(logn)$，那麼調整sz(x)的time-complexity為$O(logn)$，而因為紅黑樹本身的插入也為$O(logn)$，所以整體需要$O(logn)$的時間。
#### 3.
跟第二小題差不多的概念，我們只要更新訪問過的節點就好，從root開始，直到找到要刪除的節點，我令所有訪問過的節點的sz(x)皆減一，之後在找predecesor或是successor時，也令所有訪問過得節點的sz(x)減一，再讓predecesor(or succesor)移到要刪除的節點後並將它的sz value等於刪除的節點的sz value-1，而因為紅黑樹的高度為$O(logn)$，所以刪除以及調整sz(x)的time-complexity為$O(logn)$
#### 4.
假設要執行left-rotate(X)，且X的left-child為A而right-child為Y，Y又有其left-child B和right-child C 。於是我們可以知道在rotate前:

$sz(X)=sz(A)+sz(Y)+1=sz(A)+sz(B)+sz(C)+2$
$sz(Y)=sz(B)+sz(C)+1$

而因為node A,B,C他們在rotate之後children不變，所以$sz(A),sz(B),sz(C)$維持不變，而X的ancestor的children總數不變，所以只要考慮$sz(X)$以及$sz(Y)$的變化，而我們知道rotate之後:

$sz(X)=sz(A)+sz(B)+1$
$sz(Y)=sz(X)+sz(C)+1=sz(A)+sz(B)+sz(C)+2$

rotate-sz(x)
	a = sz(x.left)
	c = sz(y.left)
	tmp1 = sz(x)
	tmp2 = sz(y)
	sz(x) = tmp2-c+a
	sz(y) = tmp1

可以看出rotate-sz(x)的time-complexity是 $O(1)$
#### 5

int find_kth_largest(rb *root ,int k){
    if(k == sz(root->right)+1 )
	return root->value;
    else if (k <= sz(root->right) )
	return find_kth_largest(root->right , k);
    else
	return find_kth_largest(root->left , k-sz(root->right)-1 );
}

分成三種情況：
***(a)*** : 依照RB tree的建構規則，root的左子孫皆小於他；右子孫皆大於他，所以如果k等於sz(root->right)+1的話，root就是該子樹k'th largest element
***(b)*** : 假如k小於等於sz(root->right)的話，就代表我們要尋找的在右子樹中，由於右小孩皆大於root，所以我們找的還是右子樹裡的k'th largest element,以遞迴帶入。
***\(c\)*** : 如果k大於sz(root->right)+1的話，代表k'th largest element 在左子樹中，由於root跟root的右小孩全大於root的左小孩，所以我們改為尋找左子樹中(k-sz(root->right)-1)'th largest element，同樣以遞迴帶入。

-----------

### Problem 2. Strongly Connected Component
#### 1

#### 2
strongly connected component在reverve後依舊是strongly connected,那麼能夠reduce的點集合先reverese再reduce跟先reduce再reverse會是一樣的結果。

#### 3

#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
#define Slen 1000
typedef struct Edge{
	int index;
	struct Edge *next;
}edge;
typedef struct Vertex{
	edge *next;
	int color;
	int pi;
	int d;
	int f;
}vertex;
int N;
vertex V[MAXN];
vertex reversingV[MAXN];
int ts;
int Stack[Slen] = {0};
int ptr = -1;
int gr = 1;
int SSC[MAXN];
void Push(int data){
	Stack[++ptr] = data;
}
int Pop(){
	return Stack[ptr--];
}
void DFS_visit(int u){
	++ts;
	V[u].d = ts;
	V[u].color = 1;
	edge *next = V[u].next;
	while(next != NULL){
		if(V[next->index].color == 0){
			V[next->index].pi = u;
			DFS_visit(next->index);
		}
		next = next->next;
	}
	V[u].color = 2;
	++ts;
	V[u].f = ts;
	Push(u);
}
void DFS(){
	for(int i=0;i<N;i++){
		V[i].color = 0;
		V[i].pi = -1;
	}
	ts = 0;
	for(int i=0;i<N;i++)
		if(V[i].color == 0)
			DFS_visit(i);
}
void build_edge(vertex cur[] , int x ,int y){
	edge *new = (edge*)malloc(sizeof(edge));
	new->index = y;
	new->next = cur[x].next;
	cur[x].next = new;
}
void reverse_DFS_visit(int u){
	++ts;
	reversingV[u].d = ts;
	reversingV[u].color = 1;
	edge *next = reversingV[u].next;
	while(next != NULL){
		if(reversingV[next->index].color == 0){
			SSC[next->index] = gr;
			reversingV[next->index].pi = u;
			reverse_DFS_visit(next->index);
		}
		next = next->next;
	}
	reversingV[u].color = 2;
	++ts;
	reversingV[u].f = ts;
}
void find_SSC(){
	int v;
	ts = 0;
	for(int i=0;i<N;i++){
		reversingV[i].color = 0;
		reversingV[i].pi = -1;
	}
	while(ptr != -1){
		v = Pop();
		//printf("%d\n",v);
		if(reversingV[v].color == 0){
			SSC[v] = gr;
			reverse_DFS_visit(v);
			gr++;
		}
	}
}
int main(){
	int edge_N;
	int x,y;
	scanf("%d%d",&N,&edge_N);
	for(int i=0;i<edge_N;i++){
		scanf("%d%d",&x,&y);
		build_edge(V,x,y);
		build_edge(reversingV,y,x);
	}
	DFS();
	//printf("%d\n",ptr);
	find_SSC();
	for(int i=0;i<N;i++)
		printf("%d'th vertex is in group %d\n",i,SSC[i]);
	return 0;
}

在V & reversingV 的build_edge中的time-complexity是 $O(E)$
DFS的方面time-complexity $O(V+E)$
find_SSC的方面只是作reversingV 的DFS，所以也是 $O(V+E)$
print SSC的部份是 $O(V)$
所以整個code的time-complexity就是 $O(V+E)$