---
disqus: temurbekkhujaev
---

# Kosaraju

## Kirish

Yo'nalishli $G$ graf berilgan, $V$ uchlar to'plami va $E$ qirralar to'plami.

**Kuchli bog'langan komponent** (strongly connected component) grafning shunday qismiga aytiladiki bunda har qanday $u,v \in E$ uchun $u \rightarrow v$ bajariladi, ya'ni $u$ dan $v$ ga yo'l bor.

Keyinchalik *KBK* deb qisqartirib ketamiz. Anglash mumkinki grafni KBK larga bo'lganda turli xil komponentalar bir biri bilan kesishmaydi. Grafni har bir KBK larini uchlarini bitta uchga siqib yangi graf hosil qilish **kondensatsiyalash** deyiladi. Kondetsatiya qilingan graf $G^{KBK}$ ko'rinishida yoziladi. Kondetsatsiyadan keyin graf **asiklik** ko'rinishga keladi ya'ni grafda sikllar qolmaydi. Isboti shundaki agar KBK lar sikl hosil qilsa demak shu siklni tashkil qiluvchi har bir KBK dan shu sikldagi boshqa KBK larga yo'l bor va bu o'z o'rnida kuchli bog'langan komponentalarning belgisi, demak ular alohida KBK bo'lishi mumkin emas.

**Kosaraju** algoritmi grafdagi KBK larni topishda ishlatiladi.
## Algoritm

Quyida keltirilgan algoritm realizatsiyasi $O(n+m)$ vaqt va xotira talab qiladi.

Algoritmning asosiy ideyasi shundaki kuchli bog'langan komponentalar $C_1$ va $C_2$ o'rtasida qirra bo'lishi mumkin qachonki grafdagi uchlar topologik saralanganda $C < C'$ bo'lsa. Bundan kelib chiqadiki $C_1 < C_2$ shart bajarilgan holda $C_2$dan $C_1$ga qirra mavjud bo'lsa, demak $C_1$ va $C_2$ bitta KBK da yotadi aks holda har xil.

Grafni uchlari $v \in G$ uchun topologik saralab, saralangan tartibda har bitta $v$ uchun faqat shu komponentaga kiradigan va boshqalariga kirmaydigan $u$ larni topish uchun DFS qila olsak maqsadga erishamiz.

Yuqorida ko'rsatilgandek DFS qila olish uchun biz qirralari **teskarilangan graf** $G^T$qurib shu grafda $v$ bora oladigan va hali komponentasi topilmagan $u$ larni qidirishimiz kerak.

Endi algoritmni quyidagi qadamlar orqali ko'rsatish mumkin.
1. $G$ graf uchlarini topologik saralash
2. Saralangan uchlar tartibida $G^T$ grafda *DFS* qilish va shu fazada tashrif buyurilgan uchlarni yangi komponenta sifatida belgilash
## Realizatsiya

const int N = 1000001; #grafdagi uchlar maksimal uchlar soni

vector<int> g[N];     #original graf
vector<int> gr[N];    #teskarilangan graf
vector<int> comp_members[N]; #KBK a'zolarini saqlash uchun 
vector<int> order; #topologik saralangan uchlar

int comp_index[N];
bool used[N];

void topsort(int v) {
    used[v] = true;
    for (auto x:g[v]) {
        if (!used[x]) topsort(x);            
    }
    order.push_back(v);
}

void dfs(int v, int current_comp) {    
    comp_index[v] = current_comp;             # v - uchni qaysi KBK daligini belgilash
    comp_members[current_comp].push_back(v);  # KBK ga yangi element qo'shish
    for (auto x:gr[v]) {
        if (comp_index[x] == 0) {             # hali KBK topilmagan bo'lsa unda DFS qilish
            dfs(x, current_comp);
        }
    }
}

int main() {
 
    int n, m; # grafdagi uchlar va qirralar soni
    cin >> n >> m;    
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);  #original qirralar
        gr[b].push_back(a); #teskarilangan qirralar
    }
        
    for (int i = 1; i <= n; i++) { #grafni topo saralash
        if (!used[i]) topsort(i);
    }
        
    int total_comps = 0;  #grafda topilgan jami KBKlar
    
    /*  topsort dan keyin order teskari saralangan bo'ladi
        shuning uchun butun vectorni reverse qilish kerak*/
    reverse(order.begin(), order.end()); 
    
    for (auto v: order) { 
        if (comp_index[v] == 0) {
            dfs(v, ++total_comps);
        }
    }
    
    for (int c = 1; c <= total_comps; c++) { 
        cout <<"KBK " << c << ": "; 
        for (auto v:comp_member[c]) {    #c-komponenta a'zolarini chiqarish
            cout << v << ' '; 
        }
        cout << endl;
    }
    return 0;
}

## Qo'llanilishi

Kosaraju algoritmi 2SAT(2 satisfability) masalalarini yechishda qo'llaniladi, va ko'pincha grafdagi sikllardan halos bo'lish uchun kondensatsiya qilish ishlatiladi.

Quyidagi masalalarni Kosaraju orqali yechish mumkin:
https://codeforces.com/problemset/problem/427/C
https://codeforces.com/problemset/problem/505/D