Cod sursa(job #3374612)

Utilizator GabrielPetrePetre Gabriel GabrielPetre Data 9 noiembrie 2026 04:19:43
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.17 kb
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>

using namespace std;

class InParser {
private:
    FILE* fin;
    char* buff;
    int sp;
public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[32768]();
        sp = 32767;
    }
    ~InParser() {
        fclose(fin);
        delete[] buff;
    }
    InParser& operator >> (int& n) {
        char c;
        while (!isdigit(c = read_ch()));
        n = c - '0';
        while (isdigit(c = read_ch())) {
            n = n * 10 + c - '0';
        }
        return *this;
    }
private:
    char read_ch() {
        ++sp;
        if (sp == 32768) {
            sp = 0;
            fread(buff, 1, 32768, fin);
        }
        return buff[sp];
    }
};

const int MAXN = 100005;
vector<int> adj[MAXN];
int tin[MAXN], low[MAXN], timer;
bool in_stack[MAXN];
stack<int> st;
vector<vector<int>> sccs;

void dfs(int u) {
    tin[u] = low[u] = ++timer;
    st.push(u);
    in_stack[u] = true;

    for (int v : adj[u]) {
        if (!tin[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if (in_stack[v]) {
            low[u] = min(low[u], tin[v]);
        }
    }

    if (low[u] == tin[u]) {
        vector<int> current_scc;
        while (true) {
            int v = st.top();
            st.pop();
            in_stack[v] = false;
            current_scc.push_back(v);
            if (u == v) break;
        }
        sccs.push_back(current_scc);
    }
}

int main() {
    InParser fin("ctc.in");
    FILE* fout = fopen("ctc.out", "w");

    int n, m;
    fin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
    }

    for (int i = 1; i <= n; ++i) {
        if (!tin[i]) {
            dfs(i);
        }
    }

    fprintf(fout, "%zu\n", sccs.size());
    for (const auto& scc : sccs) {
        for (int node : scc) {
            fprintf(fout, "%d ", node);
        }
        fprintf(fout, "\n");
    }

    fclose(fout);
    return 0;
}