Cod sursa(job #3370869)

Utilizator papergodChivu Razvan Gabriel papergod Data 27 octombrie 2026 16:43:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.38 kb
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <stack>
#include <algorithm>
#include <fstream>

using namespace std;

struct Nod {
    int n = -1;
    vector<int> Adj;

    bool IsAdjTo(int v) {
        for (int i : Adj) {
            if (i == v) {
                return true;
            }
        }
        return false;
    }
};

struct Graph {
    bool Unoriented;
    vector<Nod> Nodes;
    int edgeCount = 0;

    Graph(bool _Unoriented = false) {
        Unoriented = _Unoriented;
    }


    void SetNodeCount(int n) {
        Nodes.resize(n);
        for (int i = 0; i < n; i++) {
            Nodes[i].n = i;
        }
    }

    int GetNodeCount() {
        return Nodes.size();
    }

    Nod& operator[] (int i) {
        return Nodes[i];
    }

    void AddEdge(int u, int v) {
        Nodes[u].Adj.push_back(v);
        if (Unoriented)
            Nodes[v].Adj.push_back(u);
        edgeCount++;
    }

    int GetEdgeCount() const {
        return edgeCount;
    }
};


void dfs(Graph& G, int v, vector<bool>& visited, vector<int>& order) {
    visited[v] = true;
    for (auto i : G[v].Adj) {
        if (!visited[i])
            dfs(G, i, visited, order);
    }
    order.push_back(v+1);
}

vector<int> sortaret(Graph &G) {
    vector<bool> visited(G.GetNodeCount(), false);
    vector<int> order;
    for (auto& i : G.Nodes) {
        if (!visited[i.n]) {
            dfs(G, i.n, visited, order);
        }
    }
    reverse(order.begin(), order.end());
    return order;
}

void ctc_dfs(Graph& G, int v, vector<int>& dfn, vector<int>& low, int& t, stack<int>& s, vector<bool>& in_stack, vector<vector<int>>& ret) {
    dfn[v] = low[v] = ++t;
    s.push(v);
    in_stack[v] = true;

    for (auto i : G[v].Adj) {
        if (dfn[i] == -1) {
            ctc_dfs(G, i, dfn, low, t, s, in_stack, ret);
            low[v] = min(low[v], low[i]);
        }
        else if (in_stack[i]) {
            low[v] = min(low[v], dfn[i]);
        }
    }

    if (low[v] == dfn[v]) {
        vector<int> cur_ctc;
        while (!s.empty()) {
            int u = s.top();
            s.pop();
            in_stack[u] = false;
            cur_ctc.push_back(u);
            if (u == v) break;
        }
        ret.push_back(cur_ctc);
    }
}

vector<vector<int>> ctc(Graph &G) {
    int t = 0;
    vector<int> dfn(G.GetNodeCount(), -1);
    vector<int> low(G.GetNodeCount(), -1);
    stack<int> s;
    vector<bool> in_stack(G.GetNodeCount(), false);
    vector<vector<int>> ret;

    for (auto& i : G.Nodes) {
        if (dfn[i.n] == -1)
            ctc_dfs(G, i.n, dfn, low, t, s, in_stack, ret);
    }

    return ret;
}

#define in fin
#define out fout

ifstream fin("ctc.in");
ofstream fout("ctc.out");

void ReadMEdges(Graph &G, int M) {
    while (M--) {
        int u, v;
        in >> u >> v;
        G.AddEdge(u-1, v-1);
    }
}

void ReadGraph(Graph &G, int N, int M) {
    G.SetNodeCount(N);
    ReadMEdges(G, M);
}


int main() {
    // Exec Count
    int T = 1;

    while (T--) {
        Graph G;
        int N, M;
        in >> N >> M;

        // Pre Graph Read

        //...

        ReadGraph(G, N, M);

        // Post Graph Read

        //...

        // Output
        auto s = ctc(G);

        out << s.size() << endl;
        for (auto i : s) {
            for (auto j : i) {
                out << j + 1 << " ";
            }
            out << endl;
        }
        //...
    }
}