Cod sursa(job #3195868)

Utilizator patrick_burasanPatrick Burasan patrick_burasan Data 21 ianuarie 2024 22:01:51
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.31 kb
#include <bits/stdc++.h>

#define pb push_back
typedef std::vector<int> vi;
typedef std::vector<vi> vii;

class InParser {
private:
    std::vector<char> str;
    int ptr;
    std::ifstream fin;

private:
    char get_char() {
        if (ptr == (int)str.size()) {
            fin.read(str.data(), (int)str.size());
            ptr = 0;
        }

        return str[ptr++];
    }

    template<class T>
    T get_int() {
        char chr;
        do {
            chr = get_char();
        } while (!isdigit(chr) && (chr != '-'));

        int sgn = +1;
        if (chr == '-') {
            sgn = -1;
            chr = get_char();
        }

        T num = 0;
        while (isdigit(chr)) {
            num = num * 10 + (chr - '0');
            chr = get_char();
        }

        return sgn * num;
    }

public:
    InParser(const char *name) : str((int)1e5), ptr((int)1e5), fin(name) { }
    ~InParser() { fin.close(); }

    template<class T>
    friend InParser &operator >> (InParser &in, T &num) {
        num = in.get_int<T>();
        return in;
    }
};

class OutParser {
private:
    std::vector<char> str;
    int ptr;
    std::ofstream fout;

private:
    void put_char(char chr) {
        if (ptr == (int)str.size()) {
            fout.write(str.data(), (int)str.size());
            ptr = 0;
        }

        str[ptr++] = chr;
    }

    template<class T>
    void put_int(T num) {
        if (num < 0) {
            put_char('-');
            num *= -1;
        }

        if (num > 9)
            put_int(num / 10);
        put_char(num % 10 + '0');
    }

public:
    OutParser(const char *name) : str((int)1e5), ptr(0), fout(name) { }
    ~OutParser() {
        fout.write(str.data(), ptr);
        fout.close();
    }

    template<class T>
    friend OutParser &operator << (OutParser &out, const T num) {
        out.put_int(num);
        return out;
    }

    friend OutParser &operator << (OutParser &out, const char chr) {
        out.put_char(chr);
        return out;
    }

    friend OutParser &operator << (OutParser &out, const char *s) {
        for (int i = 0; s[i]; i++)
            out.put_char(s[i]);
        return out;
    }
};

InParser fin("ctc.in");
OutParser fout("ctc.out");

int n, m;
std::vector<bool> vis;
std::stack<int> st;
vii adj, adj_t;
vi comp;

void load() {
    fin >> n >> m;

    adj.resize(n + 1);
    adj_t.resize(n + 1);
    vis.resize(n + 1);

    while (m--) {
        int u, v;
        fin >> u >> v;

        adj[u].pb(v);
        adj_t[v].pb(u);
    }
}

void dfs(int node, int pass) {
    vis[node] = true;

    vi &adj_list = (pass == 1) ? adj[node] : adj_t[node];

    for (auto neighbor : adj_list)
        if (!vis[neighbor])
            dfs(neighbor, pass);
    
    if (pass == 1)
        st.push(node);
    else
        comp.pb(node);
}

void kosaraju() {
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, 1);
    
    fill(vis.begin(), vis.end(), false);
    vii sol;
    while (!st.empty()) {
        int node = st.top();
        st.pop();

        if (!vis[node]) {
            dfs(node, 2);
            sol.pb(comp);
            comp.clear();
        }
    }

    fout << (int)sol.size() << '\n';
    for (auto scc : sol) {
        for (auto node : scc)
            fout << node << ' ';
        fout << '\n';
    }       
}

int main() {
    load();
    kosaraju();
    return 0;
}