Cod sursa(job #3036863)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 25 martie 2023 10:59:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.24 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;

int elapsed_time = 0;

void DFS(int node, vector<vector<int>>& edges, vector<int>& finish, vector<int>& visited) {
    elapsed_time++;
    visited[node] = 1;
    for(int neigh: edges[node])
        if (!visited[neigh]) {
            DFS(neigh, edges, finish, visited);
        }
    visited[node] = 2;
    elapsed_time++;
    finish[node] = elapsed_time;
}

void BFS(int start_node, vector<vector<int>>& edges, vector<int>& visited, vector<vector<int>>& answers) {
    answers.push_back(vector<int>{});
    
    queue<int> qu;
    visited[start_node] = 1;
    qu.push(start_node);

    while (!qu.empty()) {
        int node = qu.front();
        qu.pop();
        visited[node] = 2;
        answers.back().push_back(node);

        for(int neigh: edges[node])
            if (!visited[neigh]) {
                visited[neigh] = 1;
                qu.push(neigh);
            }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    f >> n >> m;

    vector<vector<int>> V(n + 1), VT(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b;
        f >> a >> b;
        V[a].push_back(b);
        VT[b].push_back(a);
    }

    vector<int> visited(n + 1, 0), finish(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            DFS(i, V, finish, visited);
        }
    }

    vector<pi> top;
    for (int i = 1; i <= n; i++) {
        top.push_back({ i, finish[i] });
    }
    sort(top.begin(), top.end(), [](const pi& X, const pi& Y) {
        return X.second >= Y.second;
        });
    top.resize(top.size());

    for (int i = 1; i <= n; i++) {
        visited[i] = 0;
    }

    vector<vector<int>> answers;
    for (int i = 0; i < top.size(); i++) {
        if (!visited[top[i].first]) {
            BFS(top[i].first, VT, visited, answers);
        }
    }

    g << answers.size() << '\n';
    for (vector<int>& component : answers) {
        for (int node : component)
            g << node << ' ';
        g << '\n';
    }


    return 0;
}