Cod sursa(job #3203155)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 13 februarie 2024 10:18:38
Problema Componente tare conexe Scor 12
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
#define MAXN 100000

using namespace std;

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

int n, m;
vector<vector<int>> graph;
vector<vector<int>> tgraph;
bitset<MAXN> visited;

void dfs(vector<vector<int>>& graph, int node, bitset<MAXN>& fr) {
    for (auto& neighbour: graph[node])
        if (!fr[neighbour]) {
            fr[neighbour] = true;
            dfs(graph, neighbour, fr);
        }
}

int main() {
    fin >> n >> m;

    graph = vector<vector<int>>(n, vector<int>());
    tgraph = vector<vector<int>>(n, vector<int>());
    for (int i = 0; i < m; i++) {
        int from, to;
        fin >> from >> to;
        from--, to--;
        graph[from].push_back(to);
        tgraph[to].push_back(from);
    }

    vector<vector<int>> solutions;
    for (int i = 0; i < n; i++) {
        if (visited[i])
            continue;

        bitset<MAXN> gvisited;
        bitset<MAXN> tvisited;
        dfs(graph, i, gvisited);
        dfs(tgraph, i, tvisited);
        solutions.emplace_back();
        for (int i = 0; i < n; i++)
            if (gvisited[i] && tvisited[i]) {
                solutions[solutions.size() - 1].push_back(i + 1);
                visited[i] = true;
            }
    }

    fout << solutions.size() << '\n';
    for (auto& sol: solutions) {
        for (auto& node: sol)
            fout << node << ' ';
        fout << '\n';
    }
    return 0;
}