Cod sursa(job #2968904)

Utilizator pifaDumitru Andrei Denis pifa Data 22 ianuarie 2023 12:51:51
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <vector<int>> v, vrev, ctc;

int n, m;

const int N = 1e5 + 1;

int viz[N + 1], vizrev[N + 1];

vector <int> kosaraju;

void dfs(int x)
{
    viz[x] = 1;
    for(auto i:v[x])
    {
        if(!viz[i])
            dfs(i);
    }
    kosaraju.push_back(x);
}

void dfsrev(int x)
{
    ctc.back().push_back(x);
    vizrev[x] = 1;
    for(auto i:vrev[x])
    {
        if(!vizrev[i])
        {
            vizrev[i] = 1;
            dfsrev(i);
        }
    }
}

void Kosaraju(int n)
{
    for(int i = 1; i <= n; i++)
        if(!viz[i])
          dfs(i);
    reverse(kosaraju.begin(), kosaraju.end());
    for(auto i:kosaraju)
    {
        if(!vizrev[i])
        {
            ctc.push_back({});
            dfsrev(i);
        }
    }
}

int main()
{
    in >> n >> m;
    v.resize(n + 1);
    vrev.resize(n + 1);
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;
        v[x].push_back(y);
        vrev[y].push_back(x);
    }
    Kosaraju(n);
    out << ctc.size() << '\n';
    for(int i = 0; i < ctc.size(); i++)
    {
        for(auto x:ctc[i])
            out << x << ' ';
        out << '\n';
    }
    return 0;
}