Problem 45: Strongly Connected Components

Problem Statement: Given a directed graph with n nodes and m edges, compute the number of strongly connected components (SCCs) using Kosaraju's algorithm.

Input

The first line contains two integers n and m. The next m lines each contain two integers u and v representing a directed edge from u to v.

Output

Print the number of strongly connected components in the graph.

Examples


Input:
5 5
1 2
2 3
3 1
4 5
5 4

Output:
2

Solution in C++


#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

void dfs1(int u, vector<bool> &visited, stack<int> &st, vector<vector<int>> &adj) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v])
            dfs1(v, visited, st, adj);
    }
    st.push(u);
}

void dfs2(int u, vector<bool> &visited, vector<vector<int>> &adjT) {
    visited[u] = true;
    for (int v : adjT[u]) {
        if (!visited[v])
            dfs2(v, visited, adjT);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<vector<int>> adj(n+1), adjT(n+1);
    for (int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adjT[v].push_back(u);
    }

    stack<int> st;
    vector<bool> visited(n+1, false);
    for (int i = 1; i <= n; i++){
        if (!visited[i])
            dfs1(i, visited, st, adj);
    }

    fill(visited.begin(), visited.end(), false);
    int scc_count = 0;
    while(!st.empty()){
        int u = st.top(); st.pop();
        if(!visited[u]){
            dfs2(u, visited, adjT);
            scc_count++;
        }
    }
    cout << scc_count << "\n";
    return 0;
}