Cod sursa(job #2968895)

Utilizator pifaDumitru Andrei Denis pifa Data 22 ianuarie 2023 12:28:42
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>

using namespace std;
const int nmax = 1e5 + 1;

vector<int> adj[nmax], tadj[nmax];
stack<int> s;
bool viz[nmax];
int n, m;
vector<int> comp[nmax];
int compOf[nmax];

void dfs(int nod)
{
    viz[nod] = 1;
    for (auto to : adj[nod])
    {
        if (!viz[to]) dfs(to);
    }
    s.push(nod);
}

void dfsComp(int nod, int c)
{
    viz[nod] = 1;
    comp[c].push_back(nod);
    compOf[nod] = c;
    for (auto to : tadj[nod])
    {
        if (!viz[to]) dfsComp(to, c);
    }
}

int findSCC ()
{
    for (int i = 1; i <= n; i++)
    {
        if (!viz[i]) dfs(i);
    }
    memset(viz, 0, n+1);

    int c = 0;
    while (!s.empty())
    {

        if (!viz[s.top()])
        {
            dfsComp(s.top(), ++c);
        }
        s.pop();
    }
    return c;
}

int main ()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y; cin >> x >> y;
        adj[x].push_back(y);
        tadj[y].push_back(x);
    }
    int ans = findSCC();
    cout << ans << '\n';
    for (int i = 1; i <= ans; i++)
    {
        for (auto nod : comp[i])
        {
            cout << nod << ' ';
        }
        cout << '\n';
    }
}