Cod sursa(job #3278840)

Utilizator einstein222popescu mihaela einstein222 Data 20 februarie 2025 21:02:14
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int N = 2e5 + 1;

vector<int> v[N], rev_v[N], componente(N);
stack<int> S;

int p[N], m[N];

void dfs(int nod)
{
    p[nod] = 1;
    for (int i = 0; i < v[nod].size(); i++)
    {
        if (p[v[nod][i]] == 0)
        {
            dfs(v[nod][i]);
        }
    }
}

void dfs_minus(int nod)
{
    m[nod] = 1;
    for (int i = 0; i < rev_v[nod].size(); i++)
    {
        if (m[rev_v[nod][i]] == 0)
        {
            dfs_minus(rev_v[nod][i]);
        }
    }
}

signed main()
{
    int n, M,nr_componente=0;
    in >> n >> M;
    for (int i = 1, a, b; i <= M; i++)
    {
        in >> a >> b;
        v[a].push_back(b);
        rev_v[b].push_back(a);
    }
     for(int i = 1 ; i <= n ; ++i)
        if(componente[i] == 0)
        {
            for(int j = 1; j <= n ; ++j)
                m[j] = p[j] = 0;
            nr_componente ++;
            dfs(i);
            dfs_minus(i);
            for(int j = 1; j <= n ; ++j)
                if(m[j] == 1 && p[j] == 1)
                    componente[j] = nr_componente;
        }
    out << nr_componente << '\n';
    for (int i = 1; i <= nr_componente; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (componente[j] == i)
                out << j << ' ';
        }
        out << '\n';
    }
}